比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAAAAATTT
题目名称 Asm.Def的一秒 最终得分 70
用户昵称 Satoshi 运行时间 3.348 s
代码语言 C++ 内存使用 3.17 MiB
提交时间 2015-11-02 10:43:37
显示代码纯文本
  1. #include <fstream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #define N 100010
  6. using namespace std;
  7. ifstream in("asm_second.in");
  8. ofstream out("asm_second.out");
  9. int n;
  10. int ans=0,INF=(1<<29);
  11. vector<int> G[N];
  12. bool vis[N]={0};
  13. bool l[N]={0};
  14. int f[N]={0};
  15. int fa[N]={0};
  16. class point
  17. {
  18. public:
  19. int x,y;
  20. void make(int a,int b)
  21. {
  22. x=a;
  23. y=b;
  24. }
  25. point operator -(const point a)
  26. {
  27. point b;
  28. b.x=x-a.x;
  29. b.y=y-a.y;
  30. return b;
  31. }
  32. int operator ^(const point a)
  33. {
  34. int solo=0;
  35. solo=x*a.y-y*a.x;
  36. return solo;
  37. }
  38. void print()
  39. {
  40. out<<x<<' '<<y<<endl;
  41. }
  42. }p[N],L,R;
  43. bool com(point a,point b)
  44. {
  45. if(a.x==b.x)return a.y<b.y;
  46. return a.x<b.x;
  47. }
  48. void SPFA(int s)
  49. {
  50. queue<int> q;
  51. int i,u,v;
  52. for(i=1;i<=n;i++)
  53. {
  54. l[i]=0;
  55. f[i]=-INF;
  56. }
  57. f[s]=0;
  58. q.push(s);
  59. while(!q.empty())
  60. {
  61. u=q.front();
  62. q.pop();
  63. l[u]=0;
  64. for(i=0;i<G[u].size();i++)
  65. {
  66. v=G[u][i];
  67. if(f[v]<f[u]+1)
  68. {
  69. f[v]=f[u]+1;
  70. fa[v]=u;
  71. if(!l[v])
  72. {
  73. l[v]=1;
  74. q.push(v);
  75. }
  76. }
  77. }
  78. }
  79. }
  80. void read()
  81. {
  82. int i;
  83. in>>n;
  84. in>>L.y>>L.x>>R.y>>R.x;
  85. for(i=1;i<=n;i++)in>>p[i].x>>p[i].y;
  86. p[0].make(0,0);
  87. sort(p+1,p+n+1,com);
  88. }
  89. void work()
  90. {
  91. int i,j,pos;
  92. point a,b,c;
  93. for(i=1;i<=n;i++)
  94. {
  95. a=p[i]-p[0];
  96. b=R;
  97. c=L;
  98. if((a^b)>0&&(a^c)<0)
  99. {
  100. vis[i]=1;//A在B顺时针方向
  101. G[0].push_back(i);
  102. }
  103. }
  104. for(i=1;i<=n;i++)
  105. {
  106. if(vis[i])
  107. {
  108. for(j=i+1;j<=n;j++)
  109. {
  110. if(p[j].x==p[i].x||p[j].y==p[i].y)continue;
  111. a=p[j]-p[i];
  112. b=R;
  113. c=L;
  114. if((a^b)>0&&(a^c)<0)
  115. {
  116. G[i].push_back(j);
  117. }
  118. }
  119. }
  120. }
  121. for(i=0;i<=n;i++)fa[i]=i;
  122. SPFA(0);
  123. ans=0;
  124. for(i=1;i<=n;i++)
  125. {
  126. if(f[i]>ans)
  127. {
  128. ans=f[i];
  129. pos=i;
  130. }
  131. }
  132. out<<ans<<endl;
  133. }
  134. int main()
  135. {
  136. read();
  137. work();
  138. return 0;
  139. }