fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=1000+10;
  27. const int NUM=MAX*MAX;
  28.  
  29. int n;
  30.  
  31. struct Point
  32. {
  33. 	int x,y;
  34. }d[MAX];
  35.  
  36. int tot;
  37. int num[NUM];
  38. ld ang[NUM];
  39. int val[NUM],ans[NUM];
  40.  
  41. int cmp(int a,int b)
  42. {
  43. 	return ang[a]<ang[b];
  44. }
  45.  
  46. ld Mode(ld a)
  47. {
  48. 	while(a<0)
  49. 		a+=2*M_PI;
  50. 	while(a>2*M_PI)
  51. 		a-=2*M_PI;
  52. 	return a;
  53. }
  54.  
  55. int que[MAX][MAX];
  56. int head[MAX],end[MAX];
  57.  
  58. void add(int* que,int& head,int& end,int p)
  59. {
  60. 	while(end>head && ans[ que[end-1] ] <= ans[p] )
  61. 		end--;
  62. 	que[end++]=p;
  63. }
  64.  
  65. int ask(int * que,int& head,int& end,int p)
  66. {
  67. 	while(head<end && Mode( ang[p]-ang[que[head]] ) >=M_PI)
  68. 		head++;
  69. 	if(head<end)
  70. 		return ans[que[head]];
  71. 	else return -1;
  72. }
  73.  
  74. int chaji(const Point& s,const Point& a,const Point& b)
  75. {
  76. 	return (a.x-s.x)*(b.y-s.y)-(a.y-s.y)*(b.x-s.x);
  77. }
  78.  
  79. void Work()
  80. {
  81. 	int _i;
  82. 	REP(_i,1,n)
  83. 		head[_i]=end[_i]=0;
  84. 	REP(_i,1,tot*2)
  85. 	{
  86. 		int u=num[(_i-1)%tot+1];
  87. 		int a=(u-1)/n+1;
  88. 		int b=(u-1)%n+1;
  89. 		if(a==2 && b==1)
  90. 			continue;
  91. 		if(_i>tot && ( chaji(d[1],d[2],d[b])<0 || chaji(d[1],d[2],d[a])<0 ) )
  92. 			continue;
  93. 		int val=ask(que[a],head[a],end[a],u);
  94. 		if(a==1 && b==2)
  95. 			val=0;
  96. 		if(val!=-1)
  97. 		{
  98. 			ans[u]=max(ans[u], val+1 ) ;
  99. 			if(b!=1)
  100. 				add(que[b],head[b],end[b],u);
  101. 		}
  102. 	}
  103. }
  104.  
  105. int main()
  106. {
  107. //	freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  108. 	int i,j;
  109. 	scanf("%d",&n);
  110. 	REP(i,1,n)
  111. 		scanf("%d%d",&d[i].x,&d[i].y);
  112. 	REP(i,1,n)
  113. 		REP(j,1,n)
  114. 			if(i!=j)
  115. 			{
  116. 				if(chaji(d[i],d[j],d[1])>0)
  117. 					continue;
  118. 				++tot;
  119. 				num[tot]=(i-1)*n+j;
  120. 				ang[ num[tot] ]=atan2(d[j].y-d[i].y,d[j].x-d[i].x);
  121. 			}
  122. 	ld tmp=ang[2];
  123. 	REP(i,1,n*n)
  124. 		ang[i]=Mode( tmp-ang[i] );
  125. 	REP(i,1,n*n)
  126. 		if(i!=2 && abs( ang[i] )<1e-6)
  127. 			ang[i]=2*M_PI;
  128. 	sort(num+1,num+tot+1,cmp);
  129. 	memset(ans,-1,sizeof ans);
  130. 	Work();
  131. 	int answer=1;
  132. 	REP(i,2,n)
  133. 		answer=max(answer,ans[(i-1)*n+1]);
  134. 	printf("%d\n",answer-1);
  135. 	return 0;
  136. }
  137.  
Success #stdin #stdout 0s 27272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/LM5nDt
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!