oj.uz

Submission #83578

# Submission time Handle Problem Language Result Execution time Memory
83578 2018-11-09T12:02:26 Z faceless The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 845 ms 17200 KB 
#include <bits/stdc++.h>
#define MP make_pair
#define F first
#define PB push_back
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const int mod = (int)1e9 + 7;
const int maxn = 1e4 + 4;
const ll inf = 1e18;
const pair <int, int> Oxy = {0, 0};

inline pii operator + (pii fi, pii se) {
	return {fi.F + se.F, fi.S + se.S};
}

inline pii operator - (pii fi, pii se) {
	return {fi.F - se.F, fi.S - se.S};
}

inline ll operator * (pii fi, pii se) {
	return 1ll * fi.F * se.S - 1ll * fi.S * se.F;
}

int n;
pii p[maxn], c[maxn];
const int maxm = 2e3 + 10;
int v[maxm][maxm];

inline bool isright (pii A, pii B, pii C) {
	pii AB = B - A;
	pii AC = C - A;
	return (AB * AC) < 0;
}

int district (pii pnt, int x) {
	int lo = 0, hi = n - 1;
	pii A = p[x];
	pii B = p[v[x][0]];
	while (hi - lo > 1) {
		int mid = (hi + lo) >> 1;
		pii C = p[v[x][mid]];
		if (isright (B, A, B + A - C)) {
			if (isright (B, A, pnt) and !isright (C, A, pnt))
				hi = mid;
			else
				lo = mid;
		}
		else {
			if (isright (B, A, pnt) or !isright (C, A, pnt))
				hi = mid;
			else
				lo = mid;
		}
	}
	return hi;
}

bool isindistrict (pii pnt, int x, int hi) {
	pii A = p[x];
	pii C = p[v[x][hi % (n - 1)]];
	pii B = p[v[x][hi - 1]];
	if (isright (B, A, B + A - C)) {
		if (isright (B, A, pnt) and !isright (C, A, pnt))
			return 1;
		else
			return 0;
	}
	else {
		if (isright (B, A, pnt) or (!isright (C, A, pnt)))
			return 1;
		else
			return 0;
	}
}

inline int nahiye (pii vec) {
	if (vec.F >= 0 and vec.S <= 0)
		return 4;
	if (vec.F >= 0 and vec.S >= 0)
		return 1;
	if (vec.F <= 0 and vec.S <= 0)
		return 3;
	return 2;
}
bool cmp (int fi, int se) {
	int x = nahiye (p[fi]), y = nahiye (p[se]);
	if (x != y)
		return x > y;
	return isright (Oxy, p[fi], p[se]);
}

int d[maxn];

int main (){
	int w, h;
	scanf ("%d%d", &w, &h);
	pii s;
	scanf ("%d%d", &s.F, &s.S);
	int number_of_camps;
	scanf ("%d", &number_of_camps);
	for (int i = 0; i < number_of_camps; i++)
		scanf ("%d%d", &c[i].F, &c[i].S);
	scanf ("%d", &n);
	for (int i = 0; i < n; i++)
		scanf ("%d%d", &p[i].F, &p[i].S);
	for (int i = 1; i < n; i++) {
		int r = rand() % i;
		swap (p[i], p[r]);
	}
	for (int i = 0; i < n; i++) {
		int tmp = 0;
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			v[i][tmp ++] = j;
			p[j] = p[i] - p[j];
		}
		sort (v[i], v[i] + tmp, cmp);
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			p[j] = p[j] - p[i];
			p[j] = Oxy - p[j];
		}
	}
	
	for (int i = 0; i < n; i++)
		d[i] = district (s, i);
	vector <int> ans;
	for (int i = 0; i < number_of_camps; i++) {
		bool found = 0;
		for (int j = 0; j < n; j++) {
			if (!isindistrict (c[i], j, d[j])) {
				found = 1;
				break;
			}
		}
		if (!found)
			ans.PB (i + 1);
	}
	int k = ans.size();
	printf ("%d\n", k);
	for (auto it : ans)
		printf ("%d ", it);
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &w, &h);
  ~~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &s.F, &s.S);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~
fangorn.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &number_of_camps);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &c[i].F, &c[i].S);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d", &n);
  ~~~~~~^~~~~~~~~~
fangorn.cpp:108:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &p[i].F, &p[i].S);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 792 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 792 KB Output is correct
2 Correct 2 ms 792 KB Output is correct
3 Correct 3 ms 864 KB Output is correct
4 Correct 3 ms 936 KB Output is correct
5 Correct 4 ms 936 KB Output is correct
6 Correct 4 ms 1132 KB Output is correct
7 Correct 2 ms 1132 KB Output is correct
8 Correct 2 ms 1132 KB Output is correct
9 Correct 3 ms 1132 KB Output is correct
10 Correct 6 ms 1544 KB Output is correct
11 Correct 6 ms 1684 KB Output is correct
12 Correct 7 ms 1684 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1684 KB Output is correct
2 Correct 2 ms 1684 KB Output is correct
3 Correct 2 ms 1684 KB Output is correct
4 Correct 174 ms 8536 KB Output is correct
5 Correct 30 ms 8536 KB Output is correct
6 Correct 555 ms 16668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 16668 KB Output is correct
2 Correct 845 ms 16948 KB Output is correct
3 Correct 581 ms 17136 KB Output is correct
4 Correct 584 ms 17200 KB Output is correct