Submission #126067

#	Time	Username	Problem	Language	Result	Execution time	Memory
126067		eriksuenderhauf	The Forest of Fangorn (CEOI14_fangorn)	C++11	100 / 100	46 ms	872 KiB

fangorn

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
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];

// to avoid floating point errors calculate the nearest point with integer coordinate
// where the ray starting from 'from' to 'to' intersects the boundary of the rectangle
// if t == 0 this is the start of a 'forbidden' area which means that the real intersection
// point is rounded "to the left" otherwise (t == 1) this is the end of such an area
// which means the point is rounded "ro the right"
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;
				}
			}
		}
		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};
		}
	}
	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;
	});
	vector<int> 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.push_back(a[i].ind);
			continue;
		}
		if (a[i].type == 1)
			cnt--;
		else
			cnt++;
	}
	sort(ans.begin(), ans.end());
	printf("%d\n", ans.size());
	for (int i: ans)
		printf("%d ", i);
	printf("\n");
    return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:193:27: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", 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:88:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
fangorn.cpp: In function 'int main()':
fangorn.cpp:91: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:99: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:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
fangorn.cpp:103: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