比赛 “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;
}