2483757_ac_0ms_156k.cpp

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

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define zero 0
using namespace std;

int kp, kq;
struct node
{
	int x, y;
}p[1001], q[1001];
int hp[1001], hq[1001];
int py, qy;
double lpy, rpy, lqy, rqy;

bool cmp(struct node a,struct node b)
{
	return a.x<b.x;
}

double MIN(int a,int b)
{
	return double(a<b?a:b);
}

double MAX(int a,int b)
{
	return double(a<b?b:a);
}

bool Cmpp(int a,int b)
{
	return p[a].y<p[b].y;
}

bool Cmpq(int a,int b)
{
	return q[a].y<q[b].y;
}

double calp(double mid)
{
	int i, j, a, b;
	double xl, xr, s = 0;

	for(i = py-1; i >= 0; i--)
	{
		if(p[i].y-mid>zero)
		{
			a = i+1;
			xl = p[i].x-(p[i].y-mid)*(p[i+1].x-p[i].x)/(p[i+1].y-p[i].y);
			break;
		}
	}
	for(i = py+1; i < kp; i++)
	{
		if(p[i].y-mid>zero)
		{
			b = i-1;
			xr = p[i].x-(p[i].y-mid)*(p[i-1].x-p[i].x)/(p[i-1].y-p[i].y);
			break;
		}
	}
	for(j = a; j < b; j++)
		s += p[j].x*p[j+1].y-p[j].y*p[j+1].x;
	s += p[b].x*mid-p[b].y*xr;
	s += xr*mid-mid*xl;
	s += xl*p[a].y-mid*p[a].x;
	s /= 2.0;
	if(s<0)
		s *= -1;
	return s;
}

double calq(double mid)
{
	int i, j, a, b;
	double xl, xr, s = 0;

	for(i = qy-1; i >= 0; i--)
	{
		if(q[i].y-mid>zero)
		{
			a = i+1;
			xl = q[i].x-(q[i].y-mid)*(q[i+1].x-q[i].x)/(q[i+1].y-q[i].y);
			break;
		}
	}
	for(i = qy+1; i < kq; i++)
	{
		if(q[i].y-mid>zero)
		{
			b = i-1;
			xr = q[i].x-(q[i].y-mid)*(q[i-1].x-q[i].x)/(q[i-1].y-q[i].y);
			break;
		}
	}
	for(j = a; j < b; j++)
		s += q[j].x*q[j+1].y-q[j].y*q[j+1].x;
	s += q[b].x*mid-q[b].y*xr;
	s += xr*mid-mid*xl;
	s += xl*q[a].y-mid*q[a].x;
	s /= 2.0;
	if(s<0)
		s *= -1;
	return s;
}

int main()
{
	int i, t;
	double a;

	scanf("%d",&t);
	while(t--)
	{
		scanf("%lf",&a);
		scanf("%d",&kp);
		for(i = 0; i < kp; i++)
			scanf("%d%d",&p[i].x,&p[i].y);
		sort(p,p+kp,cmp);
		py = qy = 0;
		for(i = 0; i < kp; i++)
		{
			hp[i] = i;
			if(i&&p[i].y<p[py].y)
				py = i;
		}
		lpy = rpy = lqy = rqy = -1000000000;
		for(i = 0; i < py; i++)
		{
			if(p[i].y-lpy>0)
				lpy = p[i].y;
		}
		for(i = py+1; i < kp; i++)
		{
			if(p[i].y-rpy>0)
				rpy = p[i].y;
		}
		sort(hp,hp+kp,Cmpp);
		scanf("%d",&kq);
		for(i = 0; i < kq; i++)
			scanf("%d%d",&q[i].x,&q[i].y);
		sort(q,q+kq,cmp);
		for(i = 0; i < kq; i++)
		{
			hq[i] = i;
			if(i&&q[i].y<q[qy].y)
				qy = i;
		}
		for(i = 0; i < qy; i++)
		{
			if(q[i].y-lqy>0)
				lqy = q[i].y;
		}
		for(i = qy+1; i < kq; i++)
		{
			if(q[i].y-rqy>0)
				rqy = q[i].y;
		}
		sort(hq,hq+kq,Cmpq);
		double min, max, mid;
		double ap, aq;
		min = MIN(p[hp[0]].y,q[hq[0]].y);
		max = MAX(p[hp[kp-1]].y,q[hq[kq-1]].y);
		while(min-max<zero)
		{
			if(fabs(min-max)<1e-6)
			{
				mid = (min+max)/2;
				break;
			}
			if(min-lpy>zero||min-lqy>zero||min-rpy>zero||min-rqy>zero)
			{
				mid = MIN(MIN(lpy,lqy),MIN(rpy,rqy));
				break;
			}
			mid = (max+min)/2;
			if(mid-lpy>zero||mid-lqy>zero||mid-rpy>zero||mid-rqy>zero)
			{
				max = mid;
				continue;
			}
			ap = 0;
			if(mid>p[hp[0]].y)
			{
				ap = calp(mid);
				if(ap-a>zero)
				{
					max = mid;
					continue;
				}
			}
			aq =ap;
			if(mid>q[hq[0]].y)
				aq += calq(mid);
			if(aq-a>zero)
				max = mid;
			else
				if(aq-a<zero)
					min = mid;
				else
					break;
		}
		printf("%.3lf\n",mid);
	}
	return 1;
}