比赛 |
东方版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;
}