| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
怎么超时了,求救#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
struct abc{
int x1,y1,x2,y2;
double d,k;
}a[100000];
int cmp1(const void *a,const void *b){
struct abc *c=(abc*)a;
struct abc *d=(abc*)b;
if(c->k!=d->k) return (c->k)>(d->k)?1:-1;
else {
if(c->d!=c->d) return (c->d)>(d->d)?1:-1;
else {
if((c->y2+c->x2)!=(d->y2+d->x2)) return (c->y2+c->x2)-(d->y2+d->x2);
else return (c->y1+c->x1)-(d->y1+d->x1);
}
}
}
int main() {
int t,k;
int n,i,j;
__int64 count;
scanf("%d",&t);
for(k=1;k<=t;k++){
scanf("%d",&n);
for(j=0;j<n;j++){
scanf("%d%d%d%d",&a[j].x1,&a[j].y1,&a[j].x2,&a[j].y2);
if(a[j].x1==a[j].x2) {a[j].k=10e18;a[j].d=fabs(a[j].x1);}
else {
a[j].k=(a[j].y2-a[j].y1)/(a[j].x2-a[j].x1);
a[j].d=fabs(a[j].y1-a[j].k*a[j].x1)/sqrt(a[j].k*a[j].k+1);
}
}
qsort(a,n,sizeof(a[0]),cmp1);
i=1; count=0;
while(i<n) {
j=i-1;
while(j>=0 && a[i].d==a[j].d && a[i].k==a[j].k){
if(a[i].x1+a[i].y1<a[j].x2+a[j].y2){
--j;
++count;
}
else break;
}
i++;
}
printf("Scenario #%d:\n",k);
printf("%I64d\n\n",count);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator