oj.uz

Submission #114500

# Submission time Handle Problem Language Result Execution time Memory
114500 2019-06-01T13:24:54 Z 김세빈(#2861) The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 292 ms 756 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

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

bool inside(pll pa, pll pb, pll pc, pll pd)
{
	if(ccw(pa, pb, pc) >= 0){
		if(ccw(pa, pb, pd) > 0 && ccw(pa, pd, pc) > 0) return 1;
		else return 0;
	}
	else{
		if(ccw(pa, pb, pd) > 0 || ccw(pa, pd, pc) > 0) return 1;
		else return 0;
	}
}

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(inside(P[i], P[l], g, P[j])) l = j;
			
			if(r == -1) r = j;
			else if(inside(P[i], g, P[r], P[j])) r = j;
		}
		
		for(j=1; j<=m; j++){
			if(!inside(P[i], P[l], P[r], C[j])){
				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:37: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:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &m);
  ~~~~~^~~~~~~~~~~~
fangorn.cpp:42: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:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
fangorn.cpp:48: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 256 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 384 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 256 KB Output is correct

Subtask #2
20.0 / 20.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 2 ms 256 KB Output is correct
5 Correct 2 ms 384 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 384 KB Output is correct
11 Correct 3 ms 256 KB Output is correct
12 Correct 3 ms 384 KB Output is correct

Subtask #3
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 256 KB Output is correct
4 Correct 23 ms 376 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 76 ms 384 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 432 KB Output is correct
2 Correct 186 ms 624 KB Output is correct
3 Correct 292 ms 756 KB Output is correct
4 Correct 207 ms 740 KB Output is correct