oj.uz

답안 #25916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
25916 2017-06-25T06:13:18 Z 윤교준(#1090) The Forest of Fangorn (CEOI14_fangorn) C++11
0 / 100
 486 ms 23708 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;
int CX[MAXC], CY[MAXC];
int TX[MAXN], TY[MAXN];
int N, C, W, H, GX, GY;

int main() {
	scanf("%d%d%d%d", &W, &H, &GX, &GY);
	scanf("%d", &C); for(int i = 1; i <= C; i++) scanf("%d%d", &CX[i], &CY[i]);
	scanf("%d", &N); for(int i = 1; i <= N; i++) scanf("%d%d", &TX[i], &TY[i]);
	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) {
		if(i == j) continue;
		const ll dt = ccw({GX, GY}, {TX[i], TY[i]}, {TX[j], TY[j]});
		G[dt < 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({TX[i], TY[i]}, {TX[a], TY[a]}, {TX[b], TY[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({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) &&
				   ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[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({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) &&
				   ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0) {
				   	flag = true; break;
				}
			} else {
				const int a = G[1][j][0];
				const int b = G[0][j].back();
				if(ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {TX[b], TY[b]}) < 0) {
					if(0 < ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) ||
							ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0) {
						flag = true; break;
					}
				} else {
					if(ccw({TX[a], TY[a]}, {TX[j], TY[j]}, {CX[i], CY[i]}) < 0 &&
					   0 < ccw({TX[b], TY[b]}, {TX[j], TY[j]}, {CX[i], CY[i]})) {
					   	flag = true; break;
					}
				}
			}
		}
		if(flag) continue;
		Ans.pb(i);
	}
	printf("%d\n", sz(Ans));
	if(!Ans.empty()) { for(int v : Ans) printf("%d ", v); puts(""); }
	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);
                                     ^
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("%d%d", &CX[i], &CY[i]);
                 ^
fangorn.cpp:52:76: 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("%d%d", &CX[i], &CY[i]);
                                                                            ^
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("%d%d", &TX[i], &TY[i]);
                 ^
fangorn.cpp:53:76: 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("%d%d", &TX[i], &TY[i]);
                                                                            ^

Subtask #1
0.0 / 30.0

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

Subtask #2
0.0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 20.0

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