|
|
back to boardWhy I got wa on test#4? Posted by panrui 27 Dec 2007 20:20 #include<iostream> #include<math.h> #define MAX 200000 #define N 350 using namespace std; int n; double map1[N][N]; struct node { int x,y; }point[N]; double dist(node a,node b) { return sqrt((double)((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y))); } void init() { cin>>n; int i,j; for(i=1;i<=n;i++) cin>>point[i].x>>point[i].y; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { map1[i][j]=dist(point[i],point[j]); //cout<<map1[i][j]<<" "; } //cout<<endl; } } double calck(node a,node b) { if(a.x-b.x!=0) return (a.y-b.y)/(a.x-b.x);else return -MAX; } int mid(node c,node a,node b) { if(a.x!=b.x) { if(abs(a.x-b.x)>abs(a.x-c.x)) return 1; }else if(abs(a.y-b.y)>abs(a.y-c.y)) return 1; return 0; } void solve() { int i,j,k,used[N][N]; double ans=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { ans+=map1[i][j]; used[i][j]=0; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { for(k=1;k<=n;k++) { if(i==j || j==k || i==k) continue; if(calck(point[i],point[j])==calck(point[i],point[k]) && mid(point[k],point[i],point[j]) && used[i][k]==0 && used[k][i]==0) {ans-=map1[i][k]*2;used[i][k]=1;} } } } ans/=2; cout<<(int)(ans)<<endl; } int main() { init(); solve(); return 0; } |
|
|