2088259_ac_3655ms_1632k.cc

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

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

using namespace std;

long n;
struct node
{
	double a;
	double b;
}line[100010];//用于存储斜率不为0的直线

bool LESS(struct node a,struct node b)
{
	return -1.0*a.a/a.b-(-1.0)*b.a/b.b<0;
}//按照直线于x轴的交点从小到大排序

void input()
{
	int mark, flag;
	long i, j, p;
	double 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("%lf%lf",&a,&b);
			if(b)//如果斜率不为0
			{
				line[p].a = a;
				line[p].b = b;
				p++;
			}
			else
				if(a>0)
					up++;//up表示斜率为0且位于x轴上方的直线
				else
					if(a<0)
						down++;//down表示斜率为0且位于x轴下方的直线
					else
						mark = 1;//mark表示直线y=0存在
		}
		if(p==0)//如果不存在斜率不为0的直线
		{
			if(up==down)
				printf("(-inf,+inf)\n");//如果上面的等于下面的 那中位线就是y=0;
			else
				printf("-1\n");//不然的话就是-1了
			continue;
		}
		sort(line,line+p,LESS);//如果存在斜率为0的直线，按照与x的交点排序
		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;
		}//while
		double sss, bbb;
		if(flag==0)//如果找不到为-1
		{
			printf("-1\n");
			continue;
		}
		if(mark&&up==n/2)//up==n/2则负无穷的时候y=0为中位线
		{
			sss = -1.0*line[ans].a/line[ans].b;
			if(sss<0&&sss>-0.005)
				sss = 0;
			printf("(-inf,%.2lf]\n",sss);
			continue;
		}
		if(mark&&down==n/2)//down==n/2则正无穷时y=0为中位线
		{
			sss = -1.0*line[ans].a/line[ans].b;
			if(sss<0&&sss>-0.005)
				sss = 0;
			printf("[%.2lf,+inf)\n",sss);
			continue;
		}
		if(mark==0)//如果y=0不存在 则只可能有一个交点
		{
			sss = -1.0*line[ans].a/line[ans].b;
			if(sss<0&&sss>-0.005)
				sss = 0;
			printf("[%.2lf,%.2lf]\n",sss,sss);
			continue;
		}
		long sans;//否则一定有两个交点，而且位置与之前算出来的位置相临
		mark = 0;
		if(ans==p-1)
		{
			sans = ans-1;
			goto ok;
		}
		if(ans==0)
		{
			sans = 0;
			goto ok;
		}
		
		if(ans<p-1)
		{
			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++;
			}
			N += down;
			P += up;
			if(N<=n/2&&P<=n/2)
			{
				sans = ans;
				mark = 1;
			}
		}
		if(mark==0&&ans>0)
		{
			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++;
			}
			N += down;
			P += up;
			if(N<=n/2&&P<=n/2)
				sans = ans-1;
		}
ok:	
		sss = -1.0*line[sans].a/line[sans].b;
		if(sss<0&&sss>-0.005)
			sss = 0;
		bbb = -1.0*line[sans+1].a/line[sans+1].b;
		if(bbb<0&&bbb>-0.005)
			bbb = 0;
		printf("[%.2lf,%.2lf]\n",sss,bbb);
	}
}

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