Source code for submission s785

fo.cpp

  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4.  
  5. #include<cmath>
  6. #include<cctype>
  7. #include<climits>
  8. #include<algorithm>
  9. #include<utility>
  10. #include<string>
  11.  
  12. #include<deque>
  13. #include<list>
  14. #include<map>
  15. #include<queue>
  16. #include<set>
  17. #include<stack>
  18. #include<vector>
  19. #include<complex>
  20.  
  21.  
  22. using namespace std;
  23.  
  24. #define REP(i,N) for (int i = 0; i < (N); i++)
  25. #define FOR(i,a,b) for (int i = (a); i <= (b); i++)
  26. #define FORI(i,a,b) for (int i = (a); i < (b); i++)
  27. #define FORD(i,a,b) for (int i = (a)-1; i >= (b); i--)
  28. #define DP(arg...) fprintf(stderr, ## arg)
  29.  
  30. typedef long long ll;
  31. typedef long double ld;
  32. typedef pair<int,int> ii;
  33. typedef complex<double> cpl;
  34.  
  35. int N;
  36. int T;
  37.  
  38. struct Bod{
  39. 	int x, y;
  40. 	bool operator<(const Bod& b)const{
  41. 		return x<b.x ||(x==b.x && y<b.y);
  42. 	}
  43. 	cpl cb;
  44. };
  45. Bod body[10100];
  46.  
  47. int obsah2(int b1, int b2, int b3){
  48. 		return (body[b2].x-body[b1].x)*(body[b3].y-body[b2].y)
  49. 				- (body[b2].y-body[b1].y)*(body[b3].x-body[b2].x);
  50. }
  51.  
  52. int hdelka, ddelka;
  53. int hbody[10100], dbody[10100];
  54.  
  55. int total[10100];
  56.  
  57. int get(int i){
  58. 	return total[i%T];
  59. }
  60. double getX(int i, cpl unit, cpl from){
  61. 	return ((body[get(i)].cb-from)/unit).real();
  62. }
  63. double getY(int i, cpl unit, cpl from){
  64. 	return ((body[get(i)].cb-from)/unit).imag();
  65. }
  66.  
  67. void solve() {
  68. 	REP(i,N){
  69. 		scanf("%d%d", &body[i].x, &body[i].y);
  70. 		body[i].cb = cpl(body[i].x, body[i].y);
  71. 	}
  72. 	hdelka = ddelka = 0;
  73. 	sort(body, body+N);
  74. 	REP(i,N){
  75. 		while(hdelka>=2 &&obsah2(hbody[hdelka-2], hbody[hdelka-1], i)>0)
  76. 			--hdelka;
  77. 		hbody[hdelka++] = i;
  78. 		while(ddelka>=2 &&obsah2(dbody[ddelka-2], dbody[ddelka-1], i)<0)
  79. 			--ddelka;
  80. 		dbody[ddelka++] = i;
  81. 	}
  82. 	//mame konvex obal
  83. 	for(int i=0;i<ddelka-1;++i)
  84. 		total[i]=dbody[i];
  85. 	for(int i=0;i<hdelka-1;++i)
  86. 		total[ddelka-1+i]=hbody[hdelka-i-1];
  87. 	T = hdelka+ddelka-2;
  88. 	//Mame total poradi
  89. 	//REP(i,T)
  90. 	//	printf("%d %d\n", body[total[i]].x, body[total[i]].y);
  91. 	//	printf("#\n");
  92. 	cpl from0 = body[get(0)].cb;
  93. 	cpl base0 = body[get(1)].cb-from0;
  94. 	cpl unit0 = base0/abs(base0);
  95. 	int Li=0, Ri=0, Ti = 0;
  96.  
  97. 	double Lx = getX(0, unit0, from0);
  98. 	double Rx = Lx;
  99. 	double Ty = getY(0, unit0, from0);
  100.  
  101. 	REP(i,T){
  102. 		double x = getX(i, unit0, from0);
  103. 		double y = getY(i, unit0, from0);
  104.  
  105. 		if(x < Lx)
  106. 			Lx = x, Li = i;
  107. 		if(x > Rx)
  108. 			Rx = x, Ri = i;
  109. 		if(y > Ty)
  110. 			Ty = y, Ti = i;
  111.  
  112. 	}
  113.  
  114. 	double min_peri = +INFINITY;
  115.  
  116. 	REP(i, T){
  117. 		cpl from = body[get(i)].cb;
  118. 		cpl base = body[get(i+1)].cb-from;
  119. 		cpl unit = base/abs(base);
  120.  
  121. 		Lx = getX(Li, unit, from);
  122. 		Rx = getX(Ri, unit, from);
  123. 		Ty = getY(Ti, unit, from);
  124.  
  125. 		while(getX(Li+1, unit, from)<Lx)
  126. 			Lx = getX(Li+1, unit, from), ++Li;
  127.  
  128. 		while(getX(Ri+1, unit, from)>Rx)
  129. 			Rx = getX(Ri+1, unit, from), ++Ri;
  130.  
  131. 		while(getY(Ti+1, unit, from)>Ty)
  132. 			Ty = getY(Ti+1, unit, from), ++Ti;
  133.  
  134.  
  135.  
  136. 		//printf("u %lf %lf\n", unit.real(), unit.imag());
  137. 		//printf("%lf - %lf; 0 - %lf\n", Lx, Rx, Ty);
  138.  
  139.  
  140. 		double peri = 2*(Ty + (Rx-Lx));
  141. 		if(peri<min_peri)
  142. 			min_peri = peri;
  143. 	}
  144.  
  145. 	printf("%lf\n", min_peri);
  146. }
  147.  
  148. int main() {
  149.  
  150. 	while (scanf("%d",&N) != EOF) {
  151. 		solve();
  152. 	}
  153. 	return 0;
  154. }
  155.