#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];}
void brute()
{
int i, j, k;
double ans = 0;
for(i=2;i<n;i++){
for(j=1;j<i;j++){
for(k=0;k<j;k++){
ll tmp = (ll)(x[j]-x[i])*(y[k]-y[i])-(ll)(x[k]-x[i])*(y[j]-y[i]);
if(tmp < 0)tmp = -tmp;
ans += (double)tmp/n/(n-1)/(n-2)/2;
}
}
}
printf("%.12f",ans*6);
}
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){brute();return 0;}
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;
double na = 0;
for(j=1;j<=n;j++){
int nj = ord[j];
if(j>1)na -= fmod(an[nj] - an[ord[j-1]] + 2*PI, 2*PI);
while(na < PI){
now[0] += x[ord[t]] - x[i];
now[1] += y[ord[t]] - y[i];
na += fmod(an[ord[t%n+1]] - an[ord[t]] + 2*PI, 2*PI);
t = t%n + 1;
}
now[0] -= x[nj] - x[i], now[1] -= y[nj] - y[i];
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
1356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
