My AC code !!! #include<iostream> #include<math.h> #include<algorithm> void quickSort(double x[],double y[],int left, int right) { int i = left, j = right; double tmp; double pivot = x[(left + right) / 2]; while (i <= j) { while (x[i] < pivot) i++; while (x[j] > pivot) j--; if (i <= j) { tmp = x[i]; x[i] = x[j]; x[j] = tmp; tmp = y[i]; y[i] = y[j]; y[j] = tmp; i++; j--; } }; if (left < j) quickSort(x,y,left, j); if (i < right) quickSort(x,y,i, right); } double dis(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } using namespace std; int main() { double a[305][305],x[305],y[305],max,s1; int i,j,n,k; cin>>n; for(i=1;i<=n;i++)cin>>x[i]>>y[i]; quickSort(x,y,1,n); int left=1,right=1; for(i=2;i<=n;i++) { if(x[i]==x[i-1])right++; else { sort(y+left,y+right+1); right++; left=right; } } sort(y+left,y+right+1); for(i=1;i<n;i++) for(j=i+1;j<=n;j++) a[i][j]=dis(x[i],y[i],x[j],y[j]); for(i=1;i<n-1;i++) for(j=i+1;j<n;j++) { max=a[i][j]; bool f=0; for(k=j+1;k<=n;k++) if ((x[k]-x[i])*(y[i]-y[j])==(y[k]-y[i])*(x[i]-x[j])) { if (max<a[i][k]) max=a[i][k];else a[i][k]=0; if (max<a[j][k]) max=a[j][k];else a[j][k]=0; } if (max>a[i][j]) a[i][j]=0; } s1=0; for(i=1;i<n;i++) for(j=i+1;j<=n;j++)s1+=a[i][j]; s1=s1+0.4999999999; cout<<(long long)s1; system("pause"); return 0; } Re: My AC code !!! Послано Sunnat 15 мар 2012 00:59 #include<cstdio> #include<cmath> int main() { double x[300],y[300]; double l[300][300],m,s=0; int n,k,i,j; scanf("%i",&n); for(i=0;i<n;i++) { scanf("%lf%lf",&x[i],&y[i]); j=i; while(j&&(x[j]<x[j-1]||(x[j]==x[j-1]&&y[j]<y[j-1]))) { x[j]=x[j]+x[j-1];x[j-1]=x[j]-x[j-1];x[j]=x[j]-x[j-1]; y[j]=y[j]+y[j-1];y[j-1]=y[j]-y[j-1];y[j]=y[j]-y[j-1]; j--; } } for(i=0;i<n-1;i++) for(j=0;j<n;j++) l[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); for(i=0;i<n-1;i++) { for(j=i+1;j<n;j++) { if(!l[i][j])continue; m=l[i][j]; for(k=j+1;k<n;k++) { if((x[i]-x[j])*(y[k]-y[j])==(x[k]-x[j])*(y[i]-y[j])) { (l[i][k]>m)?m=l[i][k]:l[i][k]=0; (l[j][k]>m)?m=l[j][k]:l[j][k]=0; } } if(l[i][j]<m)l[i][j]=0; s+=l[i][j]; } } printf("%.lf",s); return 0; } Re: My AC code !!! Послано ASK 16 фев 2014 19:51 There is no need to reinvent the wheel, that is a half of the program devoted to sorting can be replaced with struct P{ double x,y; }; P p[n]; F(i,n) cin >> p[i].x >> p[i].y; sort(p, p+n, [](const P& a, const P& b){ return tie(a.x,a.y) < tie(b.x,b.y); }); To reduce number of possible typos, use macros, such as #define I(x) int x; cin >> x #define F(i,n) for(int i = 0; i < (n); ++i) #define FOR(i,a,b) for(int i = (a); i < (b); ++i) Finally, "do not post AC solutions" :-) |