比赛 东方版NOIP模拟赛 评测结果 AAAAAAAAAA
题目名称 Yukari 最终得分 100
用户昵称 Satoshi 运行时间 0.336 s
代码语言 C++ 内存使用 3.46 MiB
提交时间 2015-10-28 19:31:24
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <math.h>   
#include <map>
#define N 100015
using namespace std;
ifstream in("camera.in");
ofstream out("camera.out");
int n,m=0;
int INF=(1<<28),C[2*N]={0},D[2*N]={0};
map<int,int> F;
bool l[N]={0};
int cha[N]={0},sum[N]={0};
void swap(int &a,int &b)
{
	int t;
	t=a;
	a=b;
	b=t;
}
class point
{
public:
	int x,y;
	void print()
	{
		out<<x<<' '<<y<<endl;
	}
}O[N];
int update(int a,int b,int c)//向上取整
{
	if(!a)return 0;
	if(!b)return INF;
	if(c)return int(ceil(double(a)/double(b)));
	if(!c)return int(floor(double(a)/double(b)));
}
void read()
{
	int i;
	point start,end,S,T,L,R,temp;
	in>>n;
	in>>start.x>>start.y>>end.x>>end.y;
	for(i=1;i<=n;i++)
	{
		in>>S.x>>S.y>>T.x>>T.y;
		L.x=(start.x-S.x);
		L.y=(end.x-S.x);
		R.x=(start.y-S.y);
		R.y=(end.y-S.y);
		L.x=update(L.x,T.x,1);
		L.y=update(L.y,T.x,0);
		R.x=update(R.x,T.y,1);
		R.y=update(R.y,T.y,0);
		if(L.x>L.y)swap(L.x,L.y);
		if(R.x>R.y)swap(R.x,R.y);
		if(L.x<0)L.x=0;
		if(R.x<0)R.x=0;
		temp.x=max(L.x,R.x);
		temp.y=min(L.y,R.y);
		if(temp.x==INF||temp.y==INF)continue;
		if(L.x==INF)O[++m]=R;
		if(R.x==INF)O[++m]=L;
		if(L.x==INF||R.x==INF)continue;
		if(temp.x<=temp.y)O[++m]=temp;
	}
}
void work()
{
	int i;
	int cnt=0,bnt=0,solo,orz=0,L;
	for(i=1;i<=m;i++)
	{
		cnt++;
		C[cnt]=O[i].x;
		cnt++;
		C[cnt]=O[i].y;
	}
	L=cnt;
	sort(C+1,C+L+1);
	for(i=1;i<2*m;i++)if(C[i]==C[i+1])l[i]=1;
	for(i=1;i<=2*m;i++)if(!l[i]){bnt++;D[bnt]=C[i];}
	for(i=1;i<=bnt;i++)F[D[i]]=i;
	for(i=1;i<=m;i++)
	{
		O[i].x=F[O[i].x];
		O[i].y=F[O[i].y];
	}
	for(i=1;i<=m;i++)
	{
		cha[O[i].x]++;
		cha[O[i].y+1]--;
	}
	for(i=1;i<=bnt;i++)sum[i]=sum[i-1]+cha[i];
	for(i=1;i<=bnt;i++)
	{
		if(orz<=sum[i])
		{
			orz=sum[i];
			solo=i;
		}
	}
	out<<D[solo]<<endl;
}
int main()
{
	read();
	work();
	return 0;
}