0
Your rating: None
CodeChef submission 617231 (C) 

CodeChef submission 617231 (C) plaintext list. Status: WA, problem E3, contest . By karlheinz_jung (karlheinz_jung), 2011-08-05 16:30:56.
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <math.h>
  4.  
  5. #define Q(a,b,c) (abs((b->x-a->x)*(c->y-a->y)-(c->x-a->x)*(b->y-a->y)))
  6. #define S(a) (Us[a]->x-Us[m-1]->x)*(Us[a]->x-Us[m-1]->x)+(Us[a]->y-Us[m-1]->y)*(Us[a]->y-Us[m-1]->y)
  7. #define T(a,b,c) ((b->x-a->x)*(c->y-a->y)-(b->y-a->y)*(c->x-a->x))
  8.  
  9. typedef struct {
  10. int x, y, z;
  11. double o;
  12. } U;
  13.  
  14. U p[1000100], *q[1000100];
  15.  
  16. int A(U **p1, U **p2)
  17. {
  18. if((*p1)->z||(*p2)->z)
  19. 	return(*p2)->z-(*p1)->z;
  20. if((*p1)->o>(*p2)->o)
  21. 	return -1;
  22. if((*p1)->o<(*p2)->o)
  23. 	return 1;
  24. return 0;
  25. }
  26.  
  27. int B(int n, U **Us)
  28. {
  29. int m, i=1, x, y, h;
  30. for(;i<n; i++)
  31. 	{
  32. 	x=Us[i]->x-Us[0]->x;
  33. 	if(!(y=Us[i]->y-Us[0]->y))
  34. 		Us[i]->z=x;
  35. 	else
  36. 		{
  37. 		Us[i]->z=0;
  38. 		Us[i]->o=(double)x/y;
  39. 		}
  40. 	}
  41. qsort(Us+1,n-1,sizeof(U *),(int(*)(const void *, const void *))A);
  42. if(n<3)return n;
  43. for(i=(m=1)+1; i<n; i++)
  44. 	{
  45. 	for(;(h=T(Us[m-1],Us[m],Us[i]))<=0&&m>1; m--);
  46. 	if(!h&&S(m)<S(i))
  47. 		Us[m]=Us[i];
  48. 	else
  49. 		Us[++m]=Us[i];
  50. 	}
  51. return m+1-(T(Us[m-1],Us[m],Us[0])<=0&&m>1);
  52. }
  53.  
  54. void C(int n, U **p)
  55. {
  56. int i=0, j, m=B(n,p), x=0, y, z, k, am;
  57. U *a, *b;
  58. for(;i<=m-3; i++)
  59. 	for(y=(j=i+1)+1,a=p[i]; j<=m-2; y=m-(k==m),x=(z>x)?z:x,j++)
  60. 		for(k=y+(z=0),b=p[j]; k<=m-1; z=am,k++)
  61. 			if((am=Q(a,b,p[k]))<=z)
  62. 				{
  63. 				y=k-1;
  64. 				break;
  65. 				}
  66. printf("%d\n", x);
  67. }
  68.  
  69. main()
  70. {
  71. int fall, n, j, w;
  72. U tmp, v;
  73. for(scanf("%d",&fall); fall--;)
  74. 	{
  75. 	for(j=w=!scanf("%d %d %d",&n,&p[0].x,&p[0].y),v=p[0],q[0]=&p[0]; ++j<n; scanf("%d %d",&p[j].x,&p[j].y),q[j]=&p[j],v=((p[j].y<v.y)||(p[j].y==v.y&&p[j].x<v.x))?p[w=j]:v);
  76. 	tmp=v;
  77. 	p[w]=p[0];
  78. 	p[0]=tmp;
  79. 	if(n<3)
  80. 		puts("0");
  81. 	else
  82. 		C(n,q);
  83. 	}
  84. return 0;
  85. }
  86.

Comments