Submission #5174

#	Time	Username	Problem	Language	Result	Execution time	Memory
5174		cki86201	초록색 삼각형 (YDX13_green)	C++98	0 / 1	860 ms	1352 KiB

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 / 1