oj.uz

Submission #25930

# Submission time Handle Problem Language Result Execution time Memory
25930 2017-06-25T06:39:17 Z 김현수(#1087) The Forest of Fangorn (CEOI14_fangorn) C++11
100 / 100
 656 ms 2360 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll M = 10005, N = 2005;
const pll O = pll(0, 0);

ll w, h, m, n, lft;
pll a[M], b[N], sp;
bool dd[M];

vector<pll> c;

pll operator+ (pll L, pll R) {return pll(L.X+R.X, L.Y+R.Y);}
pll operator- (pll L, pll R) {return pll(L.X-R.X, L.Y-R.Y);}
pll operator* ( ll L, pll R) {return pll(L  *R.X, L  *R.Y);}

ll ccw (pll A, pll B, pll C) {
	return (A.X*B.Y+B.X*C.Y+C.X*A.Y) - (A.Y*B.X+B.Y*C.X+C.Y*A.X);
}

bool isup (pll P) {
	if(P.Y == 0) return P.X > 0;
	return P.Y > 0;
}

bool isin (pll S, pll E, pll P) {
	if(ccw(O, S, E) < 0) return !isin(E, S, P);
	return ccw(O, S, P) > 0 && ccw(O, E, P) < 0;
}

bool cmp (pll A, pll B) {
	bool FA = isup(A), FB = isup(B);
	if(FA != FB) return FA;
	return ccw(O, A, B) > 0;
}

int main()
{
	scanf("%lld%lld%lld%lld%lld",&w,&h,&sp.X,&sp.Y,&m);
	lft = m;
	for(ll i=1;i<=m;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
	}
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&b[i].X,&b[i].Y);
	}
	for(ll i=1;i<=n;i++) {
		c.clear();
		for(ll j=1;j<=n;j++) {
			if(i == j) continue;
			c.push_back(-1*(b[j]-b[i]));
		}
		sort(c.begin(), c.end(), cmp);
		pll A, B, S = sp - b[i];
		for(ll j=0;j<c.size();j++) {
			A = c[j]; B = c[(j+1)%c.size()];
			if(isin(A, B, S)) break;
		}
		for(ll j=1;j<=m;j++) {
			if(dd[j]) continue;
			if(!isin(A, B, a[j]-b[i])) {
				lft--; dd[j] = true;
			}
		}
	}
	printf("%lld\n",lft);
	for(ll i=1;i<=m;i++) {
		if(!dd[i]) printf("%lld ",i);
	}
	puts("");
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:59:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll j=0;j<c.size();j++) {
               ^
fangorn.cpp:42:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld",&w,&h,&sp.X,&sp.Y,&m);
                                                    ^
fangorn.cpp:45:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].X,&a[i].Y);
                                    ^
fangorn.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
                  ^
fangorn.cpp:49:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&b[i].X,&b[i].Y);
                                    ^

Subtask #1
30.0 / 30.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2220 KB Output is correct
2 Correct 0 ms 2220 KB Output is correct
3 Correct 0 ms 2220 KB Output is correct
4 Correct 113 ms 2220 KB Output is correct
5 Correct 23 ms 2220 KB Output is correct
6 Correct 509 ms 2360 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 2360 KB Output is correct
2 Correct 656 ms 2360 KB Output is correct
3 Correct 549 ms 2360 KB Output is correct
4 Correct 463 ms 2360 KB Output is correct