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