2087370_wa.cc

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>

using namespace std;

long n;
struct node
{
	long a;
	long b;
}line[100001];

/*int cmp(const void *a, const void *b)
{
	struct node *aa = (struct node *)a;
	struct node *bb = (struct node *)b;
	return (bb->a*aa->b-aa->a*bb->b)>0?1:-1;
}*/

bool LESS(struct node a,struct node b)
{
	return a.b*b.a-a.a*b.b<0;
}

void input()
{
	int mark, flag;
	long i, j, p;
	long a, b, tmp;
	long up, down;
	long N, P;
	long ans;
	long st, ed;

	while(scanf("%ld",&n)==1&&n)
	{
		p = 0;mark = flag = 0;up = down = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%ld%ld",&a,&b);
			if(b)
			{
				line[p].a = a;
				line[p].b = b;
				p++;
			}
			else
				if(a>0)
					up++;
				else
					if(a<0)
						down++;
					else
						mark = 1;
		}
		if(p)
		{
		//	qsort(line,p,sizeof(line[0]),cmp);
			sort(line,line+p,LESS);
			st = 0; ed = p-1;
			while(st<=ed)
			{
				i = (st+ed)/2;
				N = P = 0;
				for(j = 0; j < p; j++)
				{
					tmp = line[j].a*line[i].b-line[i].a*line[j].b;
				    if(tmp>0)
						P++;
				    else
						if(tmp<0)
					    	N++;
				}
				N += down;
				P += up;
				if(N<=n/2&&P<=n/2)
				{
					flag = 1;
					ans = i;
					break;
				}
				else
					if(N>n/2)
						st = i+1;
					else
						ed = i-1;
			}
			if(flag)
			{
				if(mark==0)
					printf("[%.2lf,%.2lf]\n",-1.0*line[ans].a/line[ans].b,-1.0*line[ans].a/line[ans].b);
				else
				{
					if(up==n/2)
						printf("(-inf,%.2lf]\n",-1.0*line[ans].a/line[ans].b);
					else
						if(down==n/2)
							printf("[%.2lf,+inf)\n",-1.0*line[ans].a/line[ans].b);
						else
						{
							double bans, sans;
							
							if(ans==p-1)
							{
								bans = -1.0*line[ans].a/line[ans].b;
								sans = -1.0*line[ans-1].a/line[ans-1].b;
							}
							else
								if(ans==0)
								{
									bans = -1.0*line[ans+1].a/line[ans+1].b;
									sans = -1.0*line[ans].a/line[ans].b;
								}
								else
								{
									N = P = 0;
		                     		for(j = 0; j < p; j++)
									{
										tmp = line[j].a*line[ans+1].b-line[ans+1].a*line[j].b;
										if(tmp>0)
											P++;
				                        else
					                    	if(tmp<0)
					                           	N++;
									}
									if(N<=n/2&&P<=n/2)
									{
										bans = -1.0*line[ans+1].a/line[ans+1].b;
								     	sans = -1.0*line[ans].a/line[ans].b;
									}
									else
									{
										bans = -1.0*line[ans].a/line[ans].b;
							    		sans = -1.0*line[ans-1].a/line[ans-1].b;
									}
								}
							printf("[%.2lf,%.2lf]\n",sans,bans);
						}
				}	
			}
			else
				printf("-1\n");
		}
		else
		{
			if(up==down)
				printf("(-inf,+inf)\n");
			else
				printf("-1\n");
		}
	}
}

int main()
{
	input();
	return 1;
}