oj.uz

Submission #25934

# Submission time Handle Problem Language Result Execution time Memory
25934 2017-06-25T07:03:50 Z kriii The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 1293 ms 2144 KB 
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct pt{
	pt(){x = y = p = 0;};
	pt(int x_, int y_){
		x = x_; y = y_; p = -1;
		if (y == 0 && x > 0) p = 0;
		if (y > 0) p = 1;
		if (y == 0 && x < 0) p = 2;
		if (y < 0) p = 3;
	}
	int x,y,p;
	bool operator <(const pt& t) const{
		if (p != t.p) return p < t.p;
		return (long long) y * t.x < (long long) t.y * x;
	};
}P[6040];

int main()
{
	scanf ("%*d %*d");

	int x,y; scanf ("%d %d",&x,&y);
	int M, CX[10020], CY[10020];
	scanf ("%d",&M);
	for (int i=0;i<M;i++) scanf ("%d %d",&CX[i],&CY[i]);
	int N, TX[2020], TY[2020];
	scanf ("%d",&N);
	for (int i=0;i<N;i++) scanf ("%d %d",&TX[i],&TY[i]);

	vector<int> res;
	for (int i=0;i<M;i++) res.push_back(i);
	for (int i=0;i<N;i++){
		int c = 0;
		for (int j=0;j<N;j++) if (i != j){
			pt u(-(TX[j]-TX[i]),-(TY[j]-TY[i]));
			P[c++] = u;
			u.p += 4;
			P[c++] = u;
			u.p -= 8;
			P[c++] = u;
		}
		pt v(x-TX[i],y-TY[i]);
		P[c++] = v;
		sort(P,P+c);

		for (int j=0;j<c;j++) if (P[j].x == v.x && P[j].y == v.y){
			vector<int> nxt;
			for (auto &k : res){
				pt u(CX[k] - TX[i], CY[k] - TY[i]);
				if (P[j-1] < u && u < P[j+1]){nxt.push_back(k); continue;}
				u.p += 4;
				if (P[j-1] < u && u < P[j+1]){nxt.push_back(k); continue;}
				u.p -= 8;
				if (P[j-1] < u && u < P[j+1]){nxt.push_back(k); continue;}
			}
			res = nxt;
			break;
		}
	}

	printf ("%d\n",res.size());
	for (auto &x : res) printf ("%d ",++x);

	return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:65: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",res.size());
                           ^
fangorn.cpp:24:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%*d %*d");
                   ^
fangorn.cpp:26:32: 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:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&M);
                 ^
fangorn.cpp:29:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<M;i++) scanf ("%d %d",&CX[i],&CY[i]);
                                                     ^
fangorn.cpp:31:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d",&N);
                 ^
fangorn.cpp:32:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=0;i<N;i++) scanf ("%d %d",&TX[i],&TY[i]);
                                                     ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2004 KB Output is correct
2 Correct 0 ms 2004 KB Output is correct
3 Correct 0 ms 2004 KB Output is correct
4 Correct 283 ms 2004 KB Output is correct
5 Correct 56 ms 2004 KB Output is correct
6 Correct 1196 ms 2004 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 2004 KB Output is correct
2 Correct 1293 ms 2144 KB Output is correct
3 Correct 1189 ms 2144 KB Output is correct
4 Correct 903 ms 2144 KB Output is correct