| 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:51There 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" :-)
 |