제출 #126065

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126065		eriksuenderhauf	The Forest of Fangorn (CEOI14_fangorn)	C++11	100 / 100	46 ms	940 KiB

fangorn

//#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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20