Submission #453720

#	Time	Username	Problem	Language	Result	Execution time	Memory
453720		kingfran1907	The Forest of Fangorn (CEOI14_fangorn)	C++14	100 / 100	564 ms	612 KiB

fangorn

#include <bits/stdc++.h>
#define X first
#define Y second
 
using namespace std;
typedef long long llint;
 
const int maxn = 2e5+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 18;
const int off = 1 << logo;
const int treesiz = off << 1;

struct pt {
	int x, y;
	int p;
	
	pt() {x = 0, y = 0, p = 0;}
	pt(int x, int y) {
		this->x = x;
		this->y = y;
		if (y == 0) {
			if (x > 0) p = 1;
			else p = 3;
		} else {
			if (y > 0) p = 2;
			else p = 4;
		}
	}
};

bool cmp(pt a, pt b) {
	if (a.p != b.p) return a.p < b.p;
	return (llint)b.x * a.y < (llint)a.x * b.y;
}

int w, h;
int xg, yg;
int n, c;
int xc[maxn], yc[maxn];
int x[maxn], y[maxn];
vector< int > uphul, downhul;
bool sol[maxn];

int main() {
	scanf("%d%d%d%d", &w, &h, &xg, &yg);
	scanf("%d", &c);
	for (int i = 0; i < c; i++) 
		scanf("%d%d", xc+i, yc+i);
		
	scanf("%d", &n);
	for (int i = 0; i < n; i++) 
		scanf("%d%d", x+i, y+i);
	
	for (int i = 0; i < c; i++) sol[i] = true;
	for (int i = 0; i < n; i++) {
		//printf("fixing: %d (%d %d)\n", i + 1, x[i], y[i]);
		vector< pt > v;
		for (int j = 0; j < n; j++) {
			if (i == j) continue;
			pt tren(x[i] - x[j], y[i] - y[j]);
			v.push_back(tren);
		}
		
		pt ac(xg - x[i], yg - y[i]);
		v.push_back(ac);
		sort(v.begin(), v.end(), cmp);
		
		//printf("target: (%d %d)\n", ac.x, ac.y);
		//printf("debug: "); for (int j = 0; j < v.size(); j++) printf("(%d %d) ", v[j].x, v[j].y);
		//printf("\n");
		
		for (int j = 0; j < v.size(); j++) {
			if (!(v[j].x == ac.x && v[j].y == ac.y)) continue;
			pt a = v[(j - 1 + v.size()) % v.size()];
			if (j == 0) a.p -= 4;
			pt b = v[(j + 1) % v.size()];
			if (j + 1 == v.size()) b.p += 4;
			
			for (int k = 0; k < c; k++) {
				if (!sol[k]) continue;
				pt tren(xc[k] - x[i], yc[k] - y[i]);
				//printf("trying %d: (%d %d)\n", k, tren.x, tren.y);
				
				bool flag = false;
				if (cmp(a, tren) && cmp(tren, b)) flag = true;
				tren.p += 4;
				if (cmp(a, tren) && cmp(tren, b)) flag = true;
				tren.p -= 8;
				if (cmp(a, tren) && cmp(tren, b)) flag = true;
				
				//printf("eliminated %d\n", k);
				if (!flag) sol[k] = false;
			}
		}
	}
	
	int kol = 0;
	for (int i = 0; i < c; i++) kol += sol[i];
	
	printf("%d\n", kol);
	for (int i = 0; i < c; i++) 
		if (sol[i]) printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int j = 0; j < v.size(); j++) {
      |                   ~~^~~~~~~~~~
fangorn.cpp:80:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    if (j + 1 == v.size()) b.p += 4;
      |        ~~~~~~^~~~~~~~~~~
fangorn.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d%d%d", &w, &h, &xg, &yg);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d", &c);
      |  ~~~~~^~~~~~~~~~
fangorn.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%d%d", xc+i, yc+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~
fangorn.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
fangorn.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", x+i, y+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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