notさんのを見習って僕も書いてみた.
方針は zerokugiさんのと同じ.
線分をむりやり符号付きにしてやると楽なようだ.
サンプルは通った.
ライブラリ除いて50行くらい.
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0; i < (n); ++i) #define X real() #define Y imag() using R = long double; using P = complex<R>; using L = pair<P, P>; const R EPS = 1E-8; #define fst first #define snd second inline int sgn(const R &r){ return (r > EPS) - (r < -EPS); } inline int sgn(const R &a, const R &b){ return sgn(a-b); } namespace std{ bool operator<(const P &a, const P &b){ return sgn(a.X, b.X) ? a.X < b.X : sgn(a.Y, b.Y) < 0; } } inline R dot(const P &a, const P &b){ return real(conj(a) * b); } inline R det(const P &a, const P &b){ return imag(conj(a) * b); } inline P vec(const L &l){ return l.snd - l.fst; } enum CCW{FRONT = 1, RIGHT = 2, BACK = 4, LEFT = 8, ON = 16, }; inline int ccw(const L &l, const P &p){ P b = p - l.fst, c = l.snd - l.fst; if(int scr = sgn(det(c, b))) return scr < 0 ? RIGHT : LEFT; if(sgn(dot(c, b)) < 0) return BACK; return sgn(norm(c), norm(b)) < 0 ? FRONT : ON; } inline vector<P> pLL(const L &l, const L &m){ if(sgn(det(vec(l), vec(m))) == 0) return vector<P>(0); R A = det(vec(m), vec(l)); R B = det(vec(m), m.snd - l.fst); return vector<P>(1, l.fst + B / A * vec(l)); } inline P refLP(const L &l, const P &p){ return (R)(2) * (l.fst + dot(p - l.fst, vec(l)) / norm(vec(l)) * vec(l)) - p; } vector<P> cut(const vector<P> &pol, const L &l){ vector<P> res; rep(i, pol.size()-1){ P a = pol[i], b = pol[i+1]; L s(a, b); if(ccw(l, a) != RIGHT) res.emplace_back(a); if(sgn(det(vec(l), s.fst-l.fst)) * sgn(det(vec(l), s.snd-l.fst)) < 0) res.emplace_back(pLL(l, s).front()); } res.emplace_back(res.front()); return res; } bool solve(){ int n; cin >> n; if(!n) return false; vector<P> in(n); for(auto &p : in){ R x, y; cin >> x >> y; p.real(x); p.imag(y); } in.emplace_back(in.front()); pair<int, R> res(-1, 0); rep(i, n) rep(j, i){ L l((in[i] + in[j]) / (R)(2), P(0, 0)); l.snd = l.fst + P(0, 1) * (in[i] - in[j]); vector<P> a = cut(in, l); swap(l.fst, l.snd); vector<P> b = cut(in, l); for(auto &p : b) p = refLP(l, p); reverse(begin(b), end(b)); vector<P> c = b; rep(i, a.size()-1) c = cut(c, L(a[i], a[i+1])); vector<P> ps; for(auto &p : a) ps.emplace_back(p); for(auto &p : b) ps.emplace_back(p); for(auto &p : c) ps.emplace_back(p); auto near = [](const P &a, const P &b){ return sgn(abs(a-b)) == 0; }; sort(begin(ps), end(ps)); ps.erase(unique(begin(ps), end(ps), near), end(ps)); vector<pair<L, int>> ls; rep(i, a.size()-1) ls.emplace_back(L(a[i], a[i+1]), +1); rep(i, b.size()-1) ls.emplace_back(L(b[i], b[i+1]), +1); rep(i, c.size()-1) ls.emplace_back(L(c[i], c[i+1]), -1); R len = 0; for(auto &ld : ls) len += ld.snd * abs(ld.fst.snd - ld.fst.fst); map<pair<int, int>, int> es; for(auto &ld : ls){ vector<pair<P, int>> qs; rep(i, ps.size()) if(ccw(ld.fst, ps[i]) == ON) qs.emplace_back(ps[i], i); sort(begin(qs), end(qs)); rep(i, qs.size()-1) es[make_pair(qs[i].snd, qs[i+1].snd)] += ld.snd; rep(i, qs.size()-1) es[make_pair(qs[i+1].snd, qs[i].snd)] += ld.snd; } int cnt = 0; vector<vector<P>> g(ps.size()); for(auto &e : es) if(e.snd) g[e.fst.fst].emplace_back(ps[e.fst.snd]); for(auto &v : g) assert(v.size() == 0 or v.size() == 2); rep(i, g.size()) if(g[i].size() == 2) cnt += ccw(L(g[i][0], g[i][1]), ps[i]) != ON; res = max(res, make_pair(cnt, len)); } printf("%.6Lf\n", res.snd); return true; } int main(void){ while(solve()); }
去年に引き続き, チーム Sophinyan として, ACM/ICPC アジア地区予選 東京大会に参加しました.
結果は, 7完最下位の, 9 位(チーム順位) でした. 順位表
| チーム順位 | 大学順位 | 国内チーム順位 | 国内大学順位 | 解いた問題数 | 時間 |
|---|---|---|---|---|---|
| 9 | 8 | 6 | 5 | 7/11 | 1089 |
酷いバグに苦しんで, 時間さえあれば解ける問題に時間を残せなかったなど, 反省点はありますが, 健闘できたかなぁと思います.
僕は, 選手としての ICPC はこれで終わりです.
運営/手伝いをして下さった方々, スポンサーの方々, JAG の皆様, 応援して下さった皆様, それから(同じチーム, またはライバルとして)一緒に闘って下さった皆様, ありがとうございました.
以下, 詳細.
提出時刻付きの順位表とかが後悔されたら, 時刻を挿入する更新をする可能性があります.
みなさん, 来年は, Twitter ID とアイコンが書いてある名札を下げてきましょう!!!!
*1：超重要な一言を忘れていたので 2014/10/21 00:19 追記
2日目の途中から参加した.
結果は,
2日目: 一人で参加. AとD の2完で20位.
3日目: @tokoharu_sakura さん, @mikecat_mixc さんと bugnyan で参加. A-D, F-H, K の 8完で6位.
4日目: @nsd_fb さん, @yuusti さんと Tera^nyan で参加. A-F の 6完で6位
でした. 楽しかったです. (小並感)
全体を通して, ワンチャンある問題が解けないという事が多かったように思う.
ワンチャンあると感じた問題が多いという事は, 強くなるチャンスであると信じて, 精進したいです.
あと, チーム戦楽しい. またいろんな人と組んでチーム戦してみたい.
チーム組んでくれた方々, JAGの方々, 某社の方々など, 色々ありがとうございました.
後輩2人と, チーム Sophinyan として, ACM/ICPC 国内予選に参加しました.
6完/7問で, 7位(チーム順位). 順位表
| チーム順位 | 大学順位 | 解いた問題数 | 時間 |
|---|---|---|---|
| 7 | 6 | 6/7 | 26280 |
2つ目の出力ファイルのタイムスタンプは次の通り.
| A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|
| 6'57 | 17'20 | 58'22(1WA) | 82'36 | 104'58 | - | 147'06 |
なんかこんないい順位になってしまっていいんだっけという感じだった.
アジア地区予選も頑張りたい.
以下, 時系列順の詳細.
見難くてごめんなさい.
僕の記憶容量3バイトくらいしかないので, 問題聞いたタイミングとか違うかも.
最大流問題を解くアルゴリズムについて, ちょろっと書いておきます.
要約すると, 言いたいことは
の二つです. 半分自分用のメモみたいなもんです.
Dinic についてちゃんと知っている人が読むメリットは多分無いです.
ツッコミなどあれば, ぜひお願いします.
蟻本のページ番号が書いてある時は, 第二版のものです.
最大流問題を知らない人は, 蟻本(p. 188から少し)を読んで下さい.
今回は, グラフ 上で,
から
への最大流を求めたいとします.
また, ,
とします. (こんな準備要るのかな)
最大流を解くアルゴリズムの一つに, Dinic 法というヤツがあります.
Dinic 法については, とりあえず, 蟻本のコラム(p. 194)に書いてある事を把握しましょう.
ここでは, "1ステップ" というのは, 一度 bfs をしてから, もう一度 bfs をするまでを指す事にします.
ワーストケースはマジ死ぬ.
Dinic 法は使い所を間違えると辛い事になる.
例えば, 次のような条件が揃うとヤバめ.
こういう時は, Goldberg-Tarjan とか, Push/Relabel 系のアルゴリズムを使った方がよさげ.
逆に,
の場合は, 割と制約大きくても, Dinic のワーストケースを突くのが難しく, 大丈夫そう.
特に, 前に言った, 辺容量が全て同じ場合や, 二部グラフの場合など.
1. は no title の一番上から読めます.
2. は Worst case behavior of the Dinic algorithm から読めます.
3. は Topcoder.
チーム Sophinyan として, ACM/ICPC アジア地区予選 会津大会に参加.
5完最下位の, 17位(チーム順位). 順位表
| チーム順位 | 大学順位 | 国内チーム順位 | 国内大学順位 | 解いた問題数 | 時間 |
|---|---|---|---|---|---|
| 17 | 11 | 13 | 7 | 5/10 | 703 |
割と色んな人と喋れて, 楽しかった.
結果的には, 反省点はいくらでもあるけど, 当初の目標(去年のように Honorable Menthion にならず, 順位が欲しい)は達成出来て, 良かったと思う.
来年はもう少し上を目指したい.
例に依って参加記というよりただイベントを時系列順に並べた何かだが, とりあえず, 競技に関係する所だけ書こうと思う.
探索順序は
S, a, b, a, e, a, S, b, e, b, f, b, S, c, g, T, g, c, h, T, h, c, S
ではないですか？最初に g に来たときに c に戻るのはなぜでしょうか．
私が理解していない/勘違いしていたら済みません．