Submission #5174

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
5174	2014-02-13T21:33:59 Z	cki86201	초록색 삼각형 (YDX13_green)	C++	0 / 1	860 ms	1352 KB

C

#include<stdio.h>
#include<algorithm>
#include<math.h>

typedef long long ll;

const double PI = 3.141592653589793238;

int x[2020], y[2020], ord[2020];
double an[2020];
int n;

bool comp(const int &a,const int &b){return an[a] < an[b];}

inline ll ccw(int a,int b,int c)
{
	return (ll)(x[b]-x[a]) * (y[c]-y[a]) - (ll)(x[c]-x[a]) * (y[b]-y[a]);
}

int main()
{
	scanf("%d",&n);
	int i, j;
	for(i=1;i<=n;i++)scanf("%d%d",x+i,y+i);
	if(n<=2)return printf("0")&0;
	if(n<=100){
		for(i=3;i<=n;i++)for(j=2;j<i;j++)for(int k=1;k<j;k++){
			if(ccw(i,j,k) == 0){
				while(1);
			}
		}
	}
	for(i=1;i<=n;i++)ord[i] = i;
	double ans = 0;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)an[j] = atan2(y[j] - y[i], x[j] - x[i]);
		std::sort(ord+1,ord+1+n,comp);
		ll now[2] = {0,0};
		int t = 1;
		if(ord[t] == i)t = t%n + 1;
		for(j=1;j<=n;j++){
			int nj = ord[j];
			if(nj == i)continue;
			if(j != t)now[0] -= x[nj] - x[i], now[1] -= y[nj] - y[i];
			else while(ord[t] == i || t == j)t = t%n + 1;
			while(t!=j && ccw(i,ord[j],ord[t]) > 0){
				now[0] += x[ord[t]] - x[i];
				now[1] += y[ord[t]] - y[i];
				t = t%n + 1;
				if(ord[t] == i)t = t%n + 1;
			}
			ans += (double)now[1] * (x[nj] - x[i]) - (double)now[0] * (y[nj] - y[i]);
		}
	}
	printf("%.12f",ans/n/(n-1)/(n-2));
	return 0;
}

Subtask #1

0.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1352 KB	Output is correct
2	Correct	0 ms	1352 KB	Output is correct
3	Correct	0 ms	1352 KB	Output is correct
4	Correct	0 ms	1352 KB	Output is correct
5	Correct	0 ms	1352 KB	Output is correct
6	Correct	0 ms	1352 KB	Output is correct
7	Correct	0 ms	1352 KB	Output is correct
8	Correct	0 ms	1352 KB	Output is correct
9	Correct	0 ms	1352 KB	Output is correct
10	Correct	0 ms	1352 KB	Output is correct
11	Correct	152 ms	1352 KB	Output is correct
12	Correct	300 ms	1352 KB	Output is correct
13	Correct	188 ms	1352 KB	Output is correct
14	Correct	776 ms	1352 KB	Output is correct
15	Correct	76 ms	1352 KB	Output is correct
16	Correct	744 ms	1352 KB	Output is correct
17	Correct	44 ms	1352 KB	Output is correct
18	Correct	116 ms	1352 KB	Output is correct
19	Correct	196 ms	1352 KB	Output is correct
20	Correct	0 ms	1352 KB	Output is correct
21	Correct	848 ms	1352 KB	Output is correct
22	Correct	856 ms	1352 KB	Output is correct
23	Correct	852 ms	1352 KB	Output is correct
24	Correct	860 ms	1352 KB	Output is correct
25	Correct	860 ms	1352 KB	Output is correct
26	Correct	848 ms	1352 KB	Output is correct
27	Correct	860 ms	1352 KB	Output is correct
28	Correct	860 ms	1352 KB	Output is correct
29	Correct	856 ms	1352 KB	Output is correct
30	Correct	856 ms	1352 KB	Output is correct
31	Incorrect	0 ms	1352 KB	Output isn't correct