Submission #25934

#	Time	Username	Problem	Language	Result	Execution time	Memory
25934		kriii	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	1293 ms	2144 KiB

fangorn

#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 (stderr)

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 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20