fork(2) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<stack>
  4. #include<iostream>
  5. #include<math.h>
  6. using namespace std;
  7. #define ll long long int
  8. struct node
  9. {
  10. 	ll x,y;
  11. }ar[10005];
  12. node p0;
  13. void swap(node &a,node &b)
  14. {
  15. 	node temp=a;
  16. 	a=b;
  17. 	b=temp;
  18. }
  19. int orientation(node p,node q, node r)
  20. {
  21. 	ll val=((q.y-p.y)*(r.x-q.x))-((q.x-p.x)*(r.y-q.y));
  22. 	if(val==0) return 0;
  23. 	return (val>0)?1:2;
  24. }
  25. ll dist(node p,node q)
  26. {
  27. 	return ((p.x-q.x)*(p.x-q.x))+((p.y-q.y)*(p.y-q.y));
  28. }
  29. int cmp(const void* g,const void* f)
  30. {
  31. 	node *p1=(struct node*) g;
  32. 	node *p2=(struct node*) f;
  33. 	int o=orientation(p0,*p1,*p2);
  34. 	if(o==0) return (dist(p0,*p1)<=dist(p0,*p2))? -1:1;
  35. 	return (o==2)?-1:1;
  36. }
  37. node next_to(std::stack<node> &s)
  38. {
  39. 	node p1=s.top();
  40. 	s.pop();
  41. 	node p2=s.top();
  42. 	s.push(p1);
  43. 	return p2;
  44. }
  45. int main()
  46. {
  47. 	ll n,i,x,y;
  48. 	scanf("%lld",&n);
  49. 	for(i=0;i<n;i++)
  50. 	{
  51. 		//scanf("%lld%lld",&ar[i].x,&ar[i].y);
  52. 		cin>>ar[i].x>>ar[i].y;
  53. 	}
  54. 	//printf("3.%lld %lld\n",(ll)ar[8424].x,(ll)ar[8424].y);
  55. 	ll ind=0;
  56. 	for(i=1;i<n;i++)
  57. 	{
  58. 		if(ar[i].y<ar[ind].y||(ar[i].y==ar[ind].y&&ar[i].x<ar[ind].x)) ind=i;
  59. 	}
  60. 	//printf("1.%lld %lld %lld\n",ar[0].x,ar[0].y,ind);
  61. 	swap(ar[0],ar[ind]);
  62.  
  63. 	p0=ar[0];
  64. 	qsort(&ar[1],n-1,sizeof(node),cmp);
  65. 	ll m=1;
  66. 	for(ll i=1;i<n;i++)
  67. 	{
  68. 		while(i<n-1&&orientation(p0,ar[i],ar[i+1])==0) i++;
  69. 		ar[m]=ar[i];
  70. 		m++;
  71. 	}
  72. 	std::stack<node> s;
  73. 	s.push(ar[0]);
  74. 	s.push(ar[1]);
  75. 	s.push(ar[2]);
  76. 	for(i=3;i<m;i++)
  77. 	{
  78. 		while(orientation(next_to(s),s.top(),ar[i])!=2)
  79. 		s.pop();
  80. 		s.push(ar[i]);
  81. 	}
  82. 	node p1=s.top(),p3;
  83. 	p3=p1;
  84. 	ll size=s.size();
  85. 	//printf("%lld",size);
  86. 	//printf("%lld %lld\n",p1.x,p1.y);
  87. 	s.pop();
  88. 	double sum=0.0;
  89. 	while(!s.empty())
  90. 	{
  91. 		node p2=s.top();
  92. 		//printf("%lld %lld %lld %lld\n",p1.x,p1.y,p2.x,p2.y);
  93. 		sum+=sqrt((double)dist(p1,p2));
  94. 		p1=p2;
  95. 		//printf("%lld %lld\n",p1.x,p1.y);
  96. 		s.pop();
  97. 	}
  98. 	if(size>2) sum+=sqrt((double)dist(p3,p1));
  99. 	printf("%.1lf\n",sum);
  100. 	return 0;
  101. }
Runtime error #stdin #stdout 0s 4644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nDCUDc
language:
C++14 (gcc 8.3)
created:
8 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!