|
※可読性は著しく低いです
※他のライブラリの実装に激しく依存します
D aCTnc(D r, P p1, P p2) {return sig(abs((p1 + p2) / (D)2), r) <= 0 ? det(p1, p2) / 2 : r * r * arg(0, p1, p2) / 2;}
D aCT(D r, P p1, P p2) {
if (!sig(r) || near(0, p1) || near(0, p2) || near(p1, p2)) return 0;
pair<P, P> pp = pCL((C){0, r}, (L){p1, p2});
if ((p1 < pp.first) != (pp.first < p2) && (p1 < pp.second) != (pp.second < p2)) return aCTnc(r, p1, p2);
return aCTnc(r, p1, pp.first) + aCTnc(r, pp.first, pp.second) + aCTnc(r, pp.second, p2);
}
D aCPol(C c, Pol pol) {D res = 0; rep (i, pol.size()) res += aCT(c.r, pol[i] - c.c, at(pol, i + 1) - c.c); return res;}
|
３つのロープを決めてそれがピンと張る点を求めるのが難しいだけですが、実は直線の交点求めるだけでOKです。
まず、２つのロープabがピンと張る領域はz=0の平面に垂直な円になります。
３つのロープabcについて考えるとabについての円とacについての円の交点になります。
これを上から見てz=0の平面に射影してやると直線の交点になっています。
#include<iostream> #include<complex> #include<cstdio> using namespace std; #define rep(i, n) for (int i = 0; i < int(n); ++i) #define X real() #define Y imag() typedef long double D; typedef complex<D> P; struct L{P a, b;}; const D EPS = 1e-8; D det(P a, P b) {return a.X * b.Y - a.Y * b.X;} P vec(L a) {return a.b - a.a;} // 直線の交点 P pLL(L a, L b) {return a.a + vec(a) * (det(vec(b), b.a - a.a) / det(vec(b), vec(a)));} int n; P pp[11]; D l[11], res; // ２点を決めてロープがピンと張る点 P b(int i, int j) {return pp[i] + (pp[j] - pp[i]) * (norm(pp[i] - pp[j]) + l[i] * l[i] - l[j] * l[j]) / (2 * norm(pp[i] - pp[j]));} // 点を決めた時にどれだけ高くできるか求めてresを更新 void h(P p) { D r = 1e9; rep (i, n) r = min(r, sqrt(max(l[i] * l[i] - norm(pp[i] - p), (D)0))); res = max(res, r); } int main() { while (cin >> n, n) { rep (i, n) cin >> pp[i].X >> pp[i].Y >> l[i]; res = 0; // １点 rep (i, n) h(pp[i]); // ２点 rep (i, n) rep (j, i) h(b(i, j)); // ３点 rep (i, n) rep (j, i) rep (k, j) if (abs(det(pp[j] - pp[i], pp[k] - pp[i])) > EPS) { P b1 = b(i, j), b2 = b(i, k); h(pLL((L){b1, b1 + (pp[i] - pp[j]) * P(0, 1)}, (L){b2, b2 + (pp[i] - pp[k]) * P(0, 1)})); } printf("%.12Lf\n", res); } return 0; }
|
2位でした。
解いた流れとしては
しおたさんがA解いてて詰まったら一瞬交代してB書く。かわたさんはC読んで解法作ってD読んでいた。
A通ったのでBを書く。しおたさんはDへ。(9m35s)
B通ったのでかわたさんがCを書き始める。僕はEへ。(18m59s)
C通った後、しおたさんに大玉転がし以来の簡単な幾何なので先にやりますと言ってEを書き始める。(27m25s)
EバグらせたのでしおたさんにD書いてもらって紙デバッグ。(46m42s)
グローバル変数に代入しているつもりがローカル変数に代入していたことに気づいて修正。なんかまだおかしい。
acosつけ忘れてたのに気づいて修正。E通った。(1h7m38s)
Dもすぐ通ったので順位表確認。この時点で2位。F解けないとワンチャン落ちるなと思う。(1h16m42s)
全員でF考えるけど方針さっぱり浮かばないうちに0perasanが6完してた。強すぎ。(1h26m38s)
遷移考えたら森っぽくなりませんかと僕が主張したらしおたさんがアーリー法を提案したのでとりあえずライブラリ書いてもらってかわたさんとアーリー法の勉強をした。(1h49m5s)
なんか計算量やばそうだし他の解法無いかなと思ってたらかわたさんが解法思いついたけど計算量に分割数が出てきてやばそうな感じだった。
とりあえず分割数求めてみたら意外と小さくて間に合いそうなのでかわたさんに実装おねがいしてしおたさんとデバッグ。(2h20m26s)
実装終わったもののデバッグ間に合わず終了。
全体的にはいつもどおりうまく分担できてよかったです。
Eではまったので個人的には反省点の残る出来でした。
|
１月に一回くらいARCというコンテストを開いている。わりと初心者向け。問題文が日本語。
その他にもいろいろなコンテストにジャッジ環境を提供している。
ICPCやPCKの過去問が集まっている。
週１回くらいコンテストを開いている。英語。
chokudaiさんが書いた本。初心者向け。
iwiwiさんwataさんkita_masaさんが書いた本。やや難しい。ガチ勢は誰でも持ってる。
競技プログラマのブログが集まるサイト。コンテストの予定が書いてるカレンダーが便利。
競技プログラミングによく出てくるアルゴリズムのライブラリ集。
ICPC OBOG会。模擬国内予選などの開催を行なっている。
ICPC過去問の非公式難易度表。
AOJなどのオンラインジャッジの問題をコンテスト形式で解くことができる。
