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

O(nlogn)

Posted by wywcgs at 2006-08-07 00:09:12 on Problem 2932
In Reply To:放弃了~~~~~~~#52 什么方法都试过总是超时#14 谁能告诉我有什么新思路么#45 Posted by:stmoon619 at 2006-08-06 23:40:54
> #include<iostream.h>
> 
> int judge(double x1,double y1,double r1,double x2,double y2,double r2)
> {
> 	
> 	if(r1 <= r2) return 0;
> 	double t = (x1 - x2) * (x1 - x2) + (y1 - y2) *(y1 - y2);
> 	if(t < r1 *r1 +r2*r2 -2 * r1*r2 )
> 		return 1;
> 	else
> 		return 0;
> }
> int compare(const void * a,const void * b)
> {
> 	return *((int*)a)-*((int*)b);
> }
> 
> 
> void main()
> {
> 	int n;
> 	cin >> n;
> 	double *x = new double[n];
> 	double *y = new double[n];
> 	double *r = new double[n];
> 	for(int i = 0 ; i < n; i++)
> 	{
> 		cin >>r[i] ;
> 		cin >>x[i];
> 		cin >>y[i];
> 	}
> 	int * c = new int [n];
> 	int d = 0;
> 	int count = 0;
> 	for(i = 0 ; i < n ; i++)
> 	{
> 		d = 0;
> 		for(int h = 0 ; h < n; h++)
> 		{
> 			if(judge(x[h],y[h],r[h],x[i],y[i],r[i]) == 1)
> 			{
> 				d = 1;
> 				break;
> 			}
> 		}
> 		if(d == 0)
> 		{	
> 			c[count] = i+1; 
> 			count++;
> 		}
> 	}
> 	cout<<count<<endl; ;
> 	for(i = 0;i < count;i++)
> 		cout<<c[i]<<" ";
> 	delete c;
> 	delete x;
> 	delete y;
> 	delete r;
> }

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