oj.uz

답안 #25928

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25928 2017-06-25T06:34:23 Z 윤교준(#1090) The Forest of Fangorn (CEOI14_fangorn) C++11
100 / 100
 966 ms 24092 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (1100000099)
#define INFLL (1100000000000000099ll)
#define MAXN (2005)
#define MAXC (10005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
ll ccw(pll a, pll b, pll c) {
	return (a.first*b.second + b.first*c.second + c.first*a.second)
		 - (a.second*b.first + b.second*c.first + c.second*a.first);
}

vector<int> G[2][MAXN];
vector<int> Ans;
pll CP[MAXC], TP[MAXN];
pll GP;
int N, C, W, H, GX, GY;

int main() {
	scanf("%d%d%d%d", &W, &H, &GX, &GY); GP = {GX, GY};
	scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%lld%lld", &CP[i].first, &CP[i].second);
	scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%lld%lld", &TP[i].first, &TP[i].second);
	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) {
		if(i == j) continue;
		G[ccw(GP, TP[i], TP[j]) < 0][i].pb(j);
	}
	for(int i = 1; i <= N; i++) for(int j = 0; j < 2; j++)
		sort(allv(G[j][i]), [&](const int& a, const int& b) -> bool {
			return 0 < ccw(TP[i], TP[a], TP[b]);
		});
	for(int i = 1; i <= C; i++) {
		bool flag = false;
		for(int j = 1; j <= N; j++) {
			if(G[1][j].empty()) {
				if(sz(G[0][j]) < 2) continue;
				const int a = G[0][j][0];
				const int b = G[0][j].back();
				if(0 < ccw(TP[a], TP[j], CP[i]) && ccw(TP[b], TP[j], CP[i]) < 0) {
				   	flag = true; break;
				}
			} else if(G[0][j].empty()) {
				if(sz(G[1][j]) < 2) continue;
				const int a = G[1][j][0];
				const int b = G[1][j].back();
				if(0 < ccw(TP[a], TP[j], CP[i]) && ccw(TP[b], TP[j], CP[i]) < 0) {
				   	flag = true; break;
				}
			} else {
				const int a = G[0][j][0];
				const int b = G[1][j].back();
				if(ccw(TP[a], TP[j], TP[b]) < 0) {
					if(0 < ccw(TP[a], TP[j], CP[i]) && ccw(TP[b], TP[j], CP[i]) < 0) {
						flag = true; break;
					}
				} else {
					if(0 < ccw(TP[a], TP[j], CP[i]) || ccw(TP[b], TP[j], CP[i]) < 0) {
					   	flag = true; break;
					}
				}
			}
		}
		if(flag) continue;
		Ans.pb(i);
	}
	if(Ans.empty()) putchar('0');
	else {
		printf("%d\n", sz(Ans));
		printf("%d", Ans[0]); for(int i = 1; i < sz(Ans); i++) printf(" %d", Ans[i]);
	}
	return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:51:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &W, &H, &GX, &GY); GP = {GX, GY};
                                     ^
fangorn.cpp:52:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%lld%lld", &CP[i].first, &CP[i].second);
                 ^
fangorn.cpp:52:93: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%lld%lld", &CP[i].first, &CP[i].second);
                                                                                             ^
fangorn.cpp:53:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%lld%lld", &TP[i].first, &TP[i].second);
                 ^
fangorn.cpp:53:93: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%lld%lld", &TP[i].first, &TP[i].second);
                                                                                             ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2304 KB Output is correct
2 Correct 0 ms 2304 KB Output is correct
3 Correct 0 ms 2304 KB Output is correct
4 Correct 0 ms 2304 KB Output is correct
5 Correct 0 ms 2304 KB Output is correct
6 Correct 0 ms 2304 KB Output is correct
7 Correct 0 ms 2304 KB Output is correct
8 Correct 0 ms 2304 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2304 KB Output is correct
2 Correct 0 ms 2304 KB Output is correct
3 Correct 0 ms 2304 KB Output is correct
4 Correct 0 ms 2304 KB Output is correct
5 Correct 0 ms 2304 KB Output is correct
6 Correct 0 ms 2436 KB Output is correct
7 Correct 0 ms 2304 KB Output is correct
8 Correct 0 ms 2304 KB Output is correct
9 Correct 0 ms 2304 KB Output is correct
10 Correct 3 ms 2568 KB Output is correct
11 Correct 3 ms 2568 KB Output is correct
12 Correct 3 ms 2568 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2304 KB Output is correct
2 Correct 0 ms 2304 KB Output is correct
3 Correct 0 ms 2304 KB Output is correct
4 Correct 103 ms 7716 KB Output is correct
5 Correct 19 ms 3624 KB Output is correct
6 Correct 466 ms 23692 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 519 ms 23800 KB Output is correct
2 Correct 966 ms 23796 KB Output is correct
3 Correct 446 ms 23664 KB Output is correct
4 Correct 453 ms 24092 KB Output is correct