제출 #83569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83569		faceless	The Forest of Fangorn (CEOI14_fangorn)	C++14	80 / 100	3049 ms	17500 KiB

fangorn

#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};

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};
}

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

int n;
pii p[maxn], c[maxn];
vector <int> v[maxn];

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;
	while (hi - lo > 1) {
		int mid = (hi + lo) >> 1;
		pii A = p[x];
		pii B = p[v[x][0]];
		pii C = p[v[x][mid]];
		pii BA = A - B;
		pii CA = A - C;
		if (isright (B, A, B + CA)) {
			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 areinsame (int idx, pii fi, pii se) {
	return district (fi, idx) == district (se, idx);
}

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 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] = p[i] - p[j];
		}
		sort (v[i].begin(), v[i].end(), cmp);
		for (int j = 0; j < n; j++) {
			if (i == j)
				continue;
			p[j] = p[j] - p[i];
			p[j] = Oxy - p[j];
		}
	}
	
	vector <int> ans;
	for (int i = 0; i < number_of_camps; i++) {
		bool found = 0;
		for (int j = 0; j < n; j++) {
			if (!areinsame (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;
}

컴파일 시 표준 에러 (stderr) 메시지

fangorn.cpp: In function 'int district(pii, int)':
fangorn.cpp:44:7: warning: variable 'BA' set but not used [-Wunused-but-set-variable]
   pii BA = A - B;
       ^~

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