Submission #25980

#	Time	Username	Problem	Language	Result	Execution time	Memory
25980		kajebiii	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	606 ms	2456 KiB

fangorn

#include <bits/stdc++.h>
 
using namespace std;
 
#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;
 
const int MAX_N = 2e3 + 100, MAX_C = 1e4 + 100;
 
int sign(ll v) { return (v>0) - (v<0); }
struct PT {
	int x, y, p;
	PT() : x(0), y(0), p(0) {}
	PT(int xx, int yy) : x(xx), y(yy) {
		if(0 < x) {
			if(0 < y) p = 1;
			else p = 4;
		}else{
			if(0 < y) p = 2;
			else p = 3;
		}
	}
	PT operator-(const PT &o) const { return PT(x-o.x, y-o.y); }
	ll cross(const PT &o) const { return 1ll*x*o.y - 1ll*y*o.x; }
	ll dot(const PT &o) const { return 1ll*x*o.x + 1ll*y*o.y; }
	int ccw(const PT &o) const { return sign(cross(o)); }
	int ccw(const PT &a, const PT &b) const { return (a-*this).ccw(b-*this); }
	ll len2() { return dot(*this); }
	double len() { return sqrt(len2()); }
	bool operator<(const PT &o) const {
		if(p != o.p) return p < o.p;
		return ccw(o) == 1;
	}
	bool operator==(const PT &o) const {
		return x == o.x && y == o.y;
	}
};
vector<PT> Cs, Ns;
 
int W, H, N, C, X, Y; PT G;
int main() {
	cin >> W >> H >> X >> Y >> C;
	G = PT(X, Y);
	REP(i, C) {
		int x, y; scanf("%d%d", &x, &y);
		Cs.push_back(PT(x, y));
	}
	cin >> N;
	REP(i, N) {
		int x, y; scanf("%d%d", &x, &y);
		Ns.push_back(PT(x, y));
	}
 
	vector<int> Ans;
	for(int i=0; i<C; i++) Ans.push_back(i);
	for(int i=0; i<N; i++) {
		vector<PT> now;
		for(int j=0; j<N; j++) if(i != j)
			now.push_back(Ns[i] - Ns[j]);
		PT v = G - Ns[i];
		now.push_back(v);
		sort(ALL(now));

		vector<int> list;
		for(int ix=0; ix<SZ(now); ix++) {
			if(now[ix] == v) {
				int a = (ix+SZ(now)-1) % SZ(now), b = (ix+1) % SZ(now);
				PT aa = now[a], bb = now[b];
				if(ix == 0) aa.p -= 4;
				if(ix+1 == SZ(now)) bb.p += 4;
				for(int &e : Ans) {
					PT p = Cs[e] - Ns[i];
					if(aa < p && p < bb) { list.push_back(e); continue; }
					p.p += 4;
					if(aa < p && p < bb) { list.push_back(e); continue; }
					p.p -= 8;
					if(aa < p && p < bb) { list.push_back(e); continue; }
				}
				Ans.swap(list);
				break;
			}
		}
	}
 
	printf("%d\n", SZ(Ans));
	for(int x : Ans) printf("%d ", x+1);
	return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:53:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^
fangorn.cpp:58:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

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