제출 #126065

#제출 시각아이디문제언어결과실행 시간메모리
126065eriksuenderhaufThe Forest of Fangorn (CEOI14_fangorn)C++11
100 / 100
46 ms940 KiB
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e5 + 5; const double eps = 1e-9; int w, h, c, n, vis[MAXN]; ll xg, yg; pll pos[MAXN], tmp[MAXN]; struct sweep { int type, ind; // 0->start, 1->end, 2->query ll x, y; } a[MAXN]; int sgn(ll x) { if (x == 0) return 0; return x > 0 ? 1 : -1; } int ccw(pll x, pll y, pll z) { ll ret = (y.fi-x.fi) * (z.se-x.se) - (y.se-x.se) * (z.fi-x.fi); return sgn(ret); } pll corner[4]; pll f(pll from, pll to, int t) { ll dx = to.fi - from.fi, dy = to.se - from.se; if (dx == 0) { if (dy > 0) return mp(to.fi, h); return mp(to.fi, 0); } if (dy == 0) { if (dx > 0) return mp(w, to.se); return mp(0, to.se); } for (int i = 0; i < 4; i++) { int o1 = ccw(from, to, corner[i]); int o2 = ccw(from, to, corner[(i+1)%4]); if (o1 == 0 && sgn(corner[i].fi - from.fi) == sgn(dx) && sgn(corner[i].se - from.se) == sgn(dy)) return corner[i]; if (o1 != -1) continue; if (o2 != 1) continue; if (i == 1 || i == 3) { ll lo = 0, hi = h; int sgn = (i == 1) ? -1 : 1; while (lo <= hi) { ll mi = (lo+hi) / 2; o1 = ccw(from, to, mp(corner[i].fi, mi)) * sgn; if (o1 == 0) return mp(corner[i].fi, mi); if (o1 > 0) lo = mi + 1; else hi = mi - 1; } if ((t == 0 && i == 3) || (t == 1 && i == 1)) return mp(corner[i].fi, lo-1); return mp(corner[i].fi, lo); } else { ll lo = 0, hi = w; int sgn = (i == 0) ? -1 : 1; while (lo <= hi) { ll mi = (lo+hi) / 2; o1 = ccw(from, to, mp(mi, corner[i].se)) * sgn; if (o1 == 0) return mp(mi, corner[i].se); if (o1 > 0) lo = mi + 1; else hi = mi - 1; } if ((t == 0 && i == 0) || (t == 1 && i == 2)) return mp(lo, corner[i].se); return mp(lo-1, corner[i].se); } } } int main() { scanf("%d %d %lld %lld %d", &w, &h, &xg, &yg, &c); corner[0] = mp(0,0); corner[1] = mp(w,0); corner[2] = mp(w,h); corner[3] = mp(0,h); for (int i = 0; i < c; i++) { a[i].type = 2; a[i].ind = i+1; scanf("%lld %lld", &a[i].x, &a[i].y); } scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lld %lld", &pos[i].fi, &pos[i].se); for (int i = 1; i <= n; i++) { pii l=mp(0,0), r=mp(0,0); for (int j = 1; j <= n; j++) { if (i == j) continue; pll cur = mp(2 * pos[i].fi - pos[j].fi, 2 * pos[i].se - pos[j].se); tmp[j] = cur; int o = ccw(pos[i], mp(xg, yg), cur); if (o > 0) { if (l.fi == 0) l = mp(j, j); else { if (ccw(pos[i], cur, tmp[l.fi]) > 0) l.fi = j; if (ccw(pos[i], cur, tmp[l.se]) < 0) l.se = j; } } else { if (r.fi == 0) r = mp(j, j); else { if (ccw(pos[i], cur, tmp[r.fi]) < 0) r.fi = j; if (ccw(pos[i], cur, tmp[r.se]) > 0) r.se = j; } } } //cerr << "add from: " << pos[i].fi << " " << pos[i].se << "\n"; if (r.fi == 0) { tmp[l.fi] = f(pos[i], tmp[l.fi], 0); tmp[l.se] = f(pos[i], tmp[l.se], 1); a[c++] = {0, i, tmp[l.fi].fi, tmp[l.fi].se}; a[c++] = {1, i, tmp[l.se].fi, tmp[l.se].se}; } else if (l.fi == 0) { tmp[r.se] = f(pos[i], tmp[r.se], 0); tmp[r.fi] = f(pos[i], tmp[r.fi], 1); a[c++] = {0, i, tmp[r.se].fi, tmp[r.se].se}; a[c++] = {1, i, tmp[r.fi].fi, tmp[r.fi].se}; } else { tmp[l.fi] = f(pos[i], tmp[l.fi], 0); tmp[r.fi] = f(pos[i], tmp[r.fi], 1); a[c++] = {0, i, tmp[l.fi].fi, tmp[l.fi].se}; a[c++] = {1, i, tmp[r.fi].fi, tmp[r.fi].se}; } //cerr << a[c-2].type << " " << a[c-2].ind << " " << a[c-2].x << " " << a[c-2].y << "\n"; //cerr << a[c-1].type << " " << a[c-1].ind << " " << a[c-1].x << " " << a[c-1].y << "\n"; } /*for (int i = 0; i < c; i++) { cerr << i << " " << a[i].type << " " << a[i].ind << " " << a[i].x << " " << a[i].y << "\n"; }*/ sort(a, a + c, [](sweep l, sweep r) { int o1 = ccw(mp(xg, yg), mp(xg+1,yg), mp(l.x, l.y)); int o2 = ccw(mp(xg, yg), mp(xg+1,yg), mp(r.x, r.y)); if (o1 == 0) { if (l.x > xg) return true; return o1 > o2; } if (o2 == 0) { if (r.x > xg) return false; return o1 > o2; } if (o1 != o2) return o1 > o2; o1 = ccw(mp(xg, yg), mp(l.x, l.y), mp(r.x, r.y)); if (o1 != 0) return o1 > 0; if (l.type == 0) return true; if (l.type == 1) return false; if (r.type == 0) return false; if (r.type == 1) return true; return l.ind < r.ind; }); /*cerr << "\n"; for (int i = 0; i < c; i++) { cerr << i << " " << a[i].type << " " << a[i].ind << " " << a[i].x << " " << a[i].y << "\n"; }*/ vi ans; int cnt = 0; for (int i = 0; i < c; i++) { if (a[i].type == 2) continue; if (a[i].type == 1 && !vis[a[i].ind]) cnt++; if (a[i].type == 0) vis[a[i].ind] = 1; else vis[a[i].ind] ^= 1; } for (int i = 0; i < c; i++) { if (a[i].type == 2) { if (cnt == 0) ans.pb(a[i].ind); continue; } if (a[i].type == 1) cnt--; else cnt++; } sort(ans.begin(), ans.end()); pri(ans.size()); for (int i: ans) printf("%d ", i); enl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

fangorn.cpp: In function 'int main()':
fangorn.cpp:13:34: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
 #define pri(n) printf("%d\n", (n))
                               ~~~^
fangorn.cpp:224:2: note: in expansion of macro 'pri'
  pri(ans.size());
  ^~~
fangorn.cpp: In function 'std::pair<long long int, long long int> f(std::pair<long long int, long long int>, std::pair<long long int, long long int>, int)':
fangorn.cpp:109:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
fangorn.cpp: In function 'int main()':
fangorn.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld %lld %d", &w, &h, &xg, &yg, &c);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:120:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &a[i].x, &a[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
fangorn.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &pos[i].fi, &pos[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...