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