- 整数W, i in [0, W] に対して、(0, 1), (W, 1), (i, 0) で表される三角形の領域たちのXORの面積を求める。
- 1≦W≦70,000
- 図にしばし圧倒される
- ベン図みたいに重なってるので (0, 1), (W, 1), (x, y) の三角形を足したり引いたりすればよさげ
- (yが)一番下の三角形W+1個は +1倍
- その上の三角形W個は -2倍
- その上の三角形W-1個は +2倍
- ...
- 一番上の三角形1個は Wが奇数なら -2 倍、偶数なら 2 倍
- したものを足してくと XOR になる
- 各交点の高さは y=x/W と y=-x/i+1 の交点なので y=i/(i+W)
- 最後のサンプルが合わない
(あとで)
- 高さは上(y=1)からの距離なので 1-i/(i+W) なのであった。あと底辺 W をかけてなかった
- 最後のサンプル以外は偶然一致していたらしい
class TriangleXor {
public:
int theArea(int W) {
long double ans = 0;
REP(i, W+1) {
long double h = i==0 ? 1 : 1-(long double)i/(i+W);
long double K = i==0 ? 1 : 2*((i&1)?-1:1);
ans += K * 0.5 * (W+1-i) * W * h;
}
return (int)ans;
}
};
