2017-04-02

2017 TCO Round1A 1000 PolygonRotation

16:27 |

2次元平面上の凸ポリゴンが整数点座標 x[i], y[i] N 個で与えられる。ポリゴンをy軸中心に回転させたときにできる立体の体積を計算せよ。
Y軸上の点は2点与えられる。(0, Ymin), (0, Ymax)
3≦N≦50, -100≦x[i]≦100, -100≦Ymin≦y[i]≦Ymax≦100
同じ場所に2点はない。
時計回り順に与えられる。
どの3点も同じ直線上にない。

残り28分くらい
んーややこしそうだ
適当なyで切りまくって円錐台の体積の和にするんだろう
2線分の交点の式を検索。
まずはy軸に対して左側と右側の線分集合に分ける必要があろう (めんどくさい)
おわり

あとで

回転体の断面の d|x|/dy が変化する y 座標群は与えられた y 座標群 ∪ 左側をx=0で反転させた線分集合と右側の線分集合の交点
y 座標群を y でソートした上で、それぞれの y 座標に対応する |x| = max(左側のx, 右側のx) を求める
y[i], y[i+1] に対応する円錐台の体積の和が答え
落ち着いて冷静にシンプルに書いてみるとできるが本番ではなかなか時間が足りないのう。

Accepted in practice

class PolygonRotation {
	public:
	double getVolume(vector <int> x, vector <int> y) {
		int N = x.size();
		int mid;
		REP(i, N) if(x[i]==0) mid=i;
		vector<P> l, r, all;
		REP(i, N) {
			if(i<=mid) {
				r.PB(P{(double)x[i], (double)y[i]});
			}
			if(i>=mid) {
				l.PB(P{(double)-x[i], (double)y[i]});
			}
		}
		l.PB(P{(double)-x[0], (double)y[0]});
		vector<double> ys(ALL(y));
		REP(i, l.size()-1) REP(j, r.size()-1) {
			auto rv = intersection(l[i], l[i+1], r[j], r[j+1]);
			if(rv.first) {
				ys.PB(rv.second.y);
			}
		}
		sort(ALL(ys));
		vector<double> xs(ys.size());
		REP(i, ys.size()) {
			// find max x for ys[i]
			double y = ys[i];
			for(auto& e : {l, r}) {
				REP(j, e.size()-1) {
					double ra = (y - e[j].y) / (e[j+1].y-e[j].y);
					if(0 <= ra && ra <= 1) {
						xs[i] = max(xs[i], e[j].x + ra * (e[j+1].x-e[j].x));
					}
				}
			}
		}
		double ans = 0;
		REP(i, ys.size()-1) {
			double h = ys[i+1]-ys[i];
			double r1 = xs[i];
			double r2 = xs[i+1];
			ans += M_PI*h/3.0*(r1*r1+r1*r2+r2*r2);
		}
		return ans;
	}
};

kojingharangの日記

2017-04-02

2017 TCO Round1A 1000 PolygonRotation