oj.uz

Submission #114447

# Submission time Handle Problem Language Result Execution time Memory
114447 2019-06-01T11:21:41 Z 김세빈(#2861) The Forest of Fangorn (CEOI14_fangorn) C++14
80 / 100
 96 ms 640 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

pll P[2020], C[10101];
ll D[2020];
ll w, h, n, m, ans;
pll g;

ll ccw(pll pa, pll pb, pll pc)
{
	return (pa.first * pb.second + pb.first * pc.second + pc.first * pa.second) -
		(pb.first * pa.second + pc.first * pb.second + pa.first * pc.second);
}

int main()
{
	ll i, j, l, r;
	
	scanf("%lld%lld%lld%lld", &w, &h, &g.first, &g.second);
	
	scanf("%lld", &m);
	
	for(i=1; i<=m; i++){
		scanf("%lld%lld", &C[i].first, &C[i].second);
	}
	
	scanf("%lld", &n);
	
	for(i=1; i<=n; i++){
		scanf("%lld%lld", &P[i].first, &P[i].second);
	}
	
	for(i=1; i<=n; i++){
		l = r = -1;
		for(j=1; j<=n; j++) if(i != j){
			P[j] = pll(2 * P[i].first - P[j].first, 2 * P[i].second - P[j].second);
			
			if(l == -1) l = j;
			else if(ccw(P[i], g, P[l]) < 0){
				if(ccw(P[i], g, P[j]) < 0 && ccw(P[i], P[j], P[l]) < 0) l = j;
			}
			else{
				if(ccw(P[i], g, P[j]) < 0 || ccw(P[i], P[j], P[l]) < 0) l = j;
			}
			
			if(r == -1) r = j;
			else if(ccw(P[i], g, P[r]) > 0){
				if(ccw(P[i], g, P[j]) > 0 && ccw(P[i], P[j], P[r]) > 0) r = j;
			}
			else{
				if(ccw(P[i], g, P[j]) > 0 || ccw(P[i], P[j], P[r]) > 0) r = j;
			}
		}
		
		for(j=1; j<=m; j++){
			if(ccw(P[i], P[l], P[r]) > 0){
				if(ccw(P[i], P[l], C[j]) < 0 || ccw(P[i], C[j], P[r]) < 0) D[j] = 1;
			}
			else{
				if(ccw(P[i], P[l], C[j]) < 0 && ccw(P[i], C[j], P[r]) < 0) D[j] = 1;
			}
		}
		
		for(j=1; j<=n; j++){
			P[j] = pll(2 * P[i].first - P[j].first, 2 * P[i].second - P[j].second);
		}
	}
	
	for(i=1; i<=m; i++){
		ans += 1 - D[i];
	}
	
	printf("%lld\n", ans);
	
	for(i=1; i<=m; i++){
		if(!D[i]) printf("%lld ", i);
	}
	
	printf("\n");
	
	return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld", &w, &h, &g.first, &g.second);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &m);
  ~~~~~^~~~~~~~~~~~
fangorn.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &C[i].first, &C[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:31:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
fangorn.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &P[i].first, &P[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 57 ms 384 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 384 KB Output is correct
2 Incorrect 96 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -