oj.uz

Submission #25961

# Submission time Handle Problem Language Result Execution time Memory
25961 2017-06-25T08:36:11 Z 카제비(#1091) The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 629 ms 2456 KB 
#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));

//		printf("[%d %d]\n", Ns[i].x, Ns[i].y);
//		for(PT &e : now) printf("(%d %d [%d]) ", e.x, e.y, e.p); puts("");

		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;
//				printf("[%d %d (%d)] < () < [%d %d (%d)]\n", aa.x, aa.y, aa.p, bb.x, bb.y, bb.p);
				for(int &e : Ans) {
					PT p = Cs[e] - Ns[i];
//					printf("[%d] : (%d %d (%d))\n", e, p.x, p.y, p.p);
					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; }
				}
//				for(int x : list) printf("[%d] ", x); puts("");
				Ans.swap(list);
				break;
			}
		}
	}

	printf("%d\n", SZ(Ans));
	for(int x : Ans) printf("%d ", x+1);
	return 0;
}

Compilation message

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 0 ms 2024 KB Output is correct
5 Correct 0 ms 2024 KB Output is correct
6 Correct 0 ms 2024 KB Output is correct
7 Correct 0 ms 2024 KB Output is correct
8 Correct 0 ms 2024 KB Output is correct
9 Correct 0 ms 2024 KB Output is correct
10 Correct 3 ms 2024 KB Output is correct
11 Correct 3 ms 2024 KB Output is correct
12 Correct 3 ms 2024 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2024 KB Output is correct
2 Correct 0 ms 2024 KB Output is correct
3 Correct 0 ms 2024 KB Output is correct
4 Correct 106 ms 2024 KB Output is correct
5 Correct 29 ms 2024 KB Output is correct
6 Correct 439 ms 2160 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 2172 KB Output is correct
2 Correct 629 ms 2456 KB Output is correct
3 Correct 493 ms 2456 KB Output is correct
4 Correct 456 ms 2456 KB Output is correct