Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

怎么超时了,求救

Posted by hahaxiao at 2005-09-01 17:42:32 on Problem 2489
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator