比赛 |
“Asm.Def战记之太平洋”杯 |
评测结果 |
AAAAAAATTT |
题目名称 |
Asm.Def的一秒 |
最终得分 |
70 |
用户昵称 |
Satoshi |
运行时间 |
3.348 s |
代码语言 |
C++ |
内存使用 |
3.17 MiB |
提交时间 |
2015-11-02 10:43:37 |
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 100010
using namespace std;
ifstream in("asm_second.in");
ofstream out("asm_second.out");
int n;
int ans=0,INF=(1<<29);
vector<int> G[N];
bool vis[N]={0};
bool l[N]={0};
int f[N]={0};
int fa[N]={0};
class point
{
public:
int x,y;
void make(int a,int b)
{
x=a;
y=b;
}
point operator -(const point a)
{
point b;
b.x=x-a.x;
b.y=y-a.y;
return b;
}
int operator ^(const point a)
{
int solo=0;
solo=x*a.y-y*a.x;
return solo;
}
void print()
{
out<<x<<' '<<y<<endl;
}
}p[N],L,R;
bool com(point a,point b)
{
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
void SPFA(int s)
{
queue<int> q;
int i,u,v;
for(i=1;i<=n;i++)
{
l[i]=0;
f[i]=-INF;
}
f[s]=0;
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
l[u]=0;
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
if(f[v]<f[u]+1)
{
f[v]=f[u]+1;
fa[v]=u;
if(!l[v])
{
l[v]=1;
q.push(v);
}
}
}
}
}
void read()
{
int i;
in>>n;
in>>L.y>>L.x>>R.y>>R.x;
for(i=1;i<=n;i++)in>>p[i].x>>p[i].y;
p[0].make(0,0);
sort(p+1,p+n+1,com);
}
void work()
{
int i,j,pos;
point a,b,c;
for(i=1;i<=n;i++)
{
a=p[i]-p[0];
b=R;
c=L;
if((a^b)>0&&(a^c)<0)
{
vis[i]=1;//A在B顺时针方向
G[0].push_back(i);
}
}
for(i=1;i<=n;i++)
{
if(vis[i])
{
for(j=i+1;j<=n;j++)
{
if(p[j].x==p[i].x||p[j].y==p[i].y)continue;
a=p[j]-p[i];
b=R;
c=L;
if((a^b)>0&&(a^c)<0)
{
G[i].push_back(j);
}
}
}
}
for(i=0;i<=n;i++)fa[i]=i;
SPFA(0);
ans=0;
for(i=1;i<=n;i++)
{
if(f[i]>ans)
{
ans=f[i];
pos=i;
}
}
out<<ans<<endl;
}
int main()
{
read();
work();
return 0;
}