oj.uz

Submission #101032

# Submission time Handle Problem Language Result Execution time Memory
101032 2019-03-16T05:08:20 Z Bruteforceman The Forest of Fangorn (CEOI14_fangorn) C++11
80 / 100
 3000 ms 1768 KB 
#include "bits/stdc++.h"
using namespace std;

struct point {
	long long x, y;
	int id;
	point () {}
	point (long long x, long long y) : x(x), y(y) {}
	point operator + (point p) {
		return point(x + p.x, y + p.y);
	}
	point operator - (point p) {
		return point(x - p.x, y - p.y);
	}
} c[10010], t[2005];
int cnt[10010];

long long cross(point a, point b) {
	return a.x * b.y - a.y * b.x;
}
int side(point a) {
	if(a.y > 0 || (a.y == 0 && a.x >= 0)) return 0;
	else return 1;
}
bool cmp(point a, point b) {
	if(side(a) == side(b)) {
		return cross(a, b) > 0;
	} else {
		return side(a) < side(b);
	}
}

int main(int argc, char const *argv[])
{
	int w, h;
	point s;
	scanf("%d %d", &w, &h);
	scanf("%lld %lld", &s.x, &s.y);

	int C;
	scanf("%d", &C);
	for(int i = 1; i <= C; i++) {
		scanf("%lld %lld", &c[i].x, &c[i].y);
	}
	int N;
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) {
		scanf("%lld %lld", &t[i].x, &t[i].y);
	}
	for(int i = 1; i <= N; i++) {
		vector <point> v;
		for(int j = 1; j <= C; j++) {
			point p = c[j] - t[i];
			p.id = j;
			v.emplace_back(p);
		}
		for(int j = 1; j <= N; j++) {
			if(j == i) continue;
			point p = t[i] - t[j];
			p.id = 0;
			v.emplace_back(p);
		}
		point p = s - t[i];
		p.id = -1;
		v.emplace_back(p);
		sort(v.begin(), v.end(), cmp);

		int pos = 0;
		for(int j = 0; j < v.size(); j++) {
			if(v[j].id < 0) {
				pos = j;
				break;
			}
		}
		int cur = pos;
		int sz = v.size();
		while(v[cur].id != 0) {
			if(v[cur].id > 0) {
				cnt[v[cur].id] += 1;
			}
			cur = (cur + 1) % sz;
		}
		cur = pos;
		while(v[cur].id != 0) {
			if(v[cur].id > 0) {
				cnt[v[cur].id] += 1;
			}
			cur = (sz + cur - 1) % sz;
		}
	}
	int ans = 0;
	for(int i = 1; i <= C; i++) {
		if(cnt[i] == N) {
			++ans;
		}
	}
	printf("%d\n", ans);
	for(int i = 1; i <= C; i++) {
		if(cnt[i] == N) {
			printf("%d ", i);
		}
	}
	if(ans) printf("\n");
	return 0;
}

Compilation message

fangorn.cpp: In function 'int main(int, const char**)':
fangorn.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < v.size(); j++) {
                  ~~^~~~~~~~~~
fangorn.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &w, &h);
  ~~~~~^~~~~~~~~~~~~~~~~
fangorn.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld", &s.x, &s.y);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C);
  ~~~~~^~~~~~~~~~
fangorn.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &c[i].x, &c[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
fangorn.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &t[i].x, &t[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 163 ms 384 KB Output is correct
5 Correct 31 ms 384 KB Output is correct
6 Correct 614 ms 636 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1144 ms 976 KB Output is correct
2 Execution timed out 3034 ms 1768 KB Time limit exceeded
3 Halted 0 ms 0 KB -