oj.uz

답안 #83567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83567 2018-11-09T10:20:39 Z faceless The Forest of Fangorn (CEOI14_fangorn) C++14
15 / 100
 792 ms 16976 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;

pii p[maxn];
vector <int> v[maxn];

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

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

int cross(pii A, pii B, pii C){
	pii AB = B - A;
	pii AC = C - A;
	int cross = AB.F * AC.S - AB.S * AC.F;
	return -cross;
}

int rob (pii x) {
	if (x.F >= 0 and x.S >= 0)
		return 4;
	if (x.F >= 0 and x.S <= 0)
		return 3;
	if (x.F <= 0 and x.S <= 0)
		return 2;
	return 1;
}

bool cmp (int fi, int se) {
	int x = rob (p[fi]), y = rob (p[se]);
	if (x != y)
		return x > y;
	return (cross ({0, 0}, p[fi], p[se]) > 0);
}

bool isright (pii a, pii b, pii c) {
//	cout << a.F << " " << a.S << " - " << b.F << " " << b.S << " - " << c.F << " " << c.S  << " cross = " << cross (a, b, c) << endl;
	if (cross (a, b, c) > 0)
		return 1;
	return 0;
}

int n;
int district (int src, pii x) {
	int lo = 0, hi = n;
	while (hi - lo > 1) {
		int mid = (hi + lo) >> 1;
		pii AB = p[src] - p[v[src][0]];
		pii AC = p[src] - p[v[src][mid]];
//		cout << mid << " -> " << p[src].F << " " << p[src].S << " - " << AB.F << " " << AB.S << " - " << AC.F << " " << AC.S << " isright = " << isright (p[src], p[src] + AB, p[src] + AC) << endl;
		if (isright (p[src], p[src] + AB, p[src] + AC)) {
			if (isright (p[src], p[src] + AB, x) and !isright (p[src], p[src] + AC, x)) {
				hi = mid;
			}
			else {
				lo = mid;
			}
		}
		else {
			if (isright (p[src], p[src] + AB, x) or !isright (p[src], p[src] + AC, x)) {
				hi = mid;
			}
			else {
				lo = mid;
			}
		}
	}
	return hi;

}

bool isinsame (int src, pii fi, pii se) {
	if (district (src, fi) == district (src, se))
		return 1;
	return 0;
}

pii c[maxn];
int main (){
	ios_base::sync_with_stdio(false);
	int w, h;
	cin >> w >> h;
	pii s;
	cin >> s.F >> s.S;
	int number_of_camps;
	cin >> number_of_camps;
	for (int i = 0; i < number_of_camps; i++)
		cin >> c[i].F >> c[i].S;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> p[i].F >> p[i].S;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			v[i].PB (j);
			p[j].F = p[i].F - p[j].F;
			p[j].S = p[i].S - p[j].S;
		}
		sort (v[i].begin(), v[i].end(), cmp);
		for (int j = 0; j < n; j++) {
			if (j == i)
				continue;
			p[j].F -= p[i].F;
			p[j].F *= -1;
			p[j].S -= p[i].S;
			p[j].S *= -1;
		}
	}

//	isinsame (2, c[1], s);
//	return 0;

	vector <int> ans;
	for (int i = 0; i < number_of_camps; i++) {
		bool found = 0;
		for (int j = 0; j < n; j++) {
			if (!isinsame (j, c[i], s)) {
				found = 1;
				break;
			}
		}
		if (!found)
			ans.PB (i + 1);
	}
	cout << ans.size() << endl;
	for (auto it : ans)
		cout << it << " ";
	cout << endl;
}

Subtask #1
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 632 KB Output is correct
3 Correct 2 ms 704 KB Output is correct
4 Correct 3 ms 780 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 3 ms 880 KB Output is correct
8 Incorrect 3 ms 1004 KB Output isn't correct

Subtask #2
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Correct 3 ms 1004 KB Output is correct
3 Incorrect 3 ms 1004 KB Output isn't correct
4 Correct 3 ms 1004 KB Output is correct
5 Correct 3 ms 1004 KB Output is correct
6 Correct 4 ms 1020 KB Output is correct
7 Correct 2 ms 1020 KB Output is correct
8 Correct 2 ms 1020 KB Output is correct
9 Incorrect 3 ms 1020 KB Output isn't correct
10 Incorrect 7 ms 1020 KB Output isn't correct
11 Incorrect 6 ms 1020 KB Output isn't correct
12 Correct 6 ms 1020 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1020 KB Output is correct
2 Correct 2 ms 1020 KB Output is correct
3 Correct 3 ms 1020 KB Output is correct
4 Incorrect 132 ms 4860 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 792 ms 16976 KB Output isn't correct
2 Halted 0 ms 0 KB -