fork(4) download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3. #include<string.h>
  4. #include<algorithm>
  5. #include<limits.h>
  6. #include<stdlib.h>
  7. #include<map>
  8. #include<vector>
  9. using namespace std;
  10. #define mod 1000000007
  11. #define ll long long
  12. #define ull unsigned long long
  13. bool ar[100][100];
  14. struct Point
  15. {
  16.     int x;
  17.     int y;
  18. }points[100];
  19. int orientation(Point p, Point q, Point r)
  20. {
  21.     int val = (q.y - p.y) * (r.x - q.x) -
  22.               (q.x - p.x) * (r.y - q.y);
  23.  
  24.     if (val == 0) return 0;  // colinear
  25.  
  26.     return (val > 0)? 1: 2; // clock or counterclock wise
  27. }
  28. bool doIntersect(Point p1, Point q1, Point p2, Point q2)
  29. {
  30. 	/*printf("%d %d\n",p1.x,p1.y);
  31. 	printf("%d %d\n",q1.x,q1.y);
  32. 	printf("%d %d\n",p2.x,p2.y);
  33. 	printf("%d %d\n",q2.x,q2.y);*/
  34.     int o1 = orientation(p1, q1, p2);
  35.     int o2 = orientation(p1, q1, q2);
  36.     int o3 = orientation(p2, q2, p1);
  37.     int o4 = orientation(p2, q2, q1);
  38.  
  39.     if (o1 != o2 && o3 != o4)
  40.     return 1;
  41.     else return 0;
  42. }
  43. int main()
  44. {
  45. 	int t,n,b[3000][100],itr=0,flag;
  46. 	char road[100][100];
  47. 	bool visited[55];
  48. 	fill(visited,visited+55,0);
  49. 		scanf("%d",&n);
  50. 		for(int i=0;i<n;i++)
  51. 		scanf("%d%d",&points[i].x,&points[i].y);
  52. 		gets(road[0]);
  53. 		for(int i=0;i<n;i++)
  54. 		gets(road[i]);
  55. 		for(int i=0;i<n;i++)
  56. 		{
  57. 			for(int j=0;j<n;j++)
  58. 			{
  59.  
  60. 				if(road[i][j]=='Y'&&ar[i][j]==0)
  61. 				{
  62. 					ar[i][j]=1;
  63. 					ar[j][i]=1;
  64. 					b[itr][0]=1;
  65. 					b[itr][1]=i;
  66. 					b[itr][2]=j;
  67. 					visited[i]=1;
  68. 					visited[j]=1;
  69. 					int x=i,y=j;
  70. 					flag=1;
  71. 					while(flag)
  72. 					{
  73. 						flag=0;
  74. 						for(int k=0;k<n;k++)
  75. 						{
  76. 							if(road[y][k]=='Y'&&ar[y][k]==0&&visited[k]==0)
  77. 							{
  78. 								bool a=0;
  79. 								for(int w=1;w<b[itr][0];w++)
  80. 								{
  81. 									a=doIntersect(points[y],points[k],points[b[itr][w]],points[b[itr][w+1]]);
  82. 									if(a==1)
  83. 									break;
  84. 								}
  85. 								if(a==0)
  86. 								{
  87. 									b[itr][0]++;
  88. 									int o=b[itr][0];
  89. 									b[itr][o+1]=k;
  90. 									visited[k]=1;
  91. 									ar[y][k]=1;
  92. 									ar[k][y]=1;
  93. 									flag=1;
  94. 									x=y;
  95. 									y=k;
  96. 								}
  97. 							}
  98. 						}
  99. 					}
  100. 					itr++;
  101. 					fill(visited,visited+55,0);
  102.  
  103. 					/*ar[i][j]=1;flag=0;
  104. 					for(int k=0;k<n;k++)
  105. 					{
  106. 						if(road[j][k]=='Y'&&ar[j][k]==0&&k!=i)
  107. 						{
  108. 							ar[j][k]=1;
  109. 							flag=1;
  110. 							b[itr][0]=2;
  111. 							b[itr][1]=i;
  112. 							b[itr][2]=j;
  113. 							b[itr][3]=k;
  114. 							itr++;
  115. 							break;
  116. 						}
  117. 					}
  118. 					if(flag==0)
  119. 					{
  120. 						b[itr][0]=1;
  121. 						b[itr][1]=i;
  122. 						b[itr][2]=j;
  123. 						itr++;
  124. 					}*/
  125. 				}
  126. 			}
  127. 		}
  128. 		printf("%d\n",itr);
  129. 		for(int i=0;i<itr;i++)
  130. 		{
  131. 			printf("%d ",b[i][0]);
  132. 			for(int j=1;j<=b[i][0]+1;j++)
  133. 			printf("%d ",b[i][j]);
  134. 			printf("\n");
  135.  
  136. 		}
  137.  
  138. }
  139.  
Success #stdin #stdout 0s 3800KB
comments (?)
stdin
copy 
6
2 3
10 0
10 7
3 7
9 8
2 1
NNNYNY
NNYYNN
NYNYYN
YYYNYN
NNYYNY
YNNNYN
stdout
copy 
3
4 0 3 1 2 4 
3 0 5 4 3 
1 2 3
https://ideone.com/qUn0fw
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years ago
visibility:
public

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!