fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll pair<long long, long long>
  4. #define dll pair<ll,long long>
  5. #define fi first
  6. #define se second
  7. const long long inf = 1e18;
  8. const int maxn = 10+1e3;
  9. long long n,d,x,y;
  10. vector<dll> g,tam;
  11. bool cmp(dll a, dll b)
  12.  {
  13.  	if (a.fi.fi==b.fi.fi) return (a.fi.se<b.fi.se);
  14.  	return (a.fi.fi<b.fi.fi);
  15.  }
  16. bool cmp1(dll a, dll b)
  17.  {
  18.  	return (a.se<b.se);
  19.  }
  20. long long cal(ll a, ll b, ll c)
  21.  {
  22.  	return (b.fi-a.fi)*(c.se-b.se)-(c.fi-b.fi)*(b.se-a.se);
  23.  }
  24. int main(){
  25. 	ios_base::sync_with_stdio(false);
  26. 	cin.tie(NULL); cout.tie(NULL);
  27. 	freopen("TREE.INP","r",stdin);
  28. 	freopen("TREE.OUT","w",stdout);
  29. 	cin>>n;
  30. 	for (int i=1; i<=n; i++)
  31. 	 {
  32. 	 	cin>>x>>y;
  33. 	 	g.push_back({{x,y},i});
  34. 	 }
  35. 	sort (g.begin(), g.end(), cmp);
  36. 	int d=0;
  37. 	while (d<g.size()-1) 
  38. 	 {
  39. 		if (g[d].fi.fi==g[d+1].fi.fi&&g[d].fi.se==g[d+1].fi.se) g.erase(g.begin()+d);
  40. 			else d++;
  41. 	 }
  42. 	tam.push_back(g[0]);
  43. 	for (int i=1; i<n; i++) 
  44. 	 {
  45. 		while (tam.size()>=2&&cal(tam[tam.size()-2].fi, tam.back().fi, g[i].fi)>0) tam.pop_back();
  46. 		tam.push_back(g[i]);
  47. 	 }
  48. 	for (int i=n-2; i>=0; i--) 
  49. 	 {
  50. 		while (tam.size()>=2&&cal(tam[tam.size()-2].fi, tam.back().fi, g[i].fi)>0) tam.pop_back();
  51. 		tam.push_back(g[i]);
  52. 	 }
  53. 	d=1;
  54. 	while (d<tam.size()-1) 
  55. 		if (cal(tam[d-1].fi, tam[d].fi, tam[d+1].fi)==0) tam.erase(tam.begin()+d);
  56. 			else d++;
  57. 	if (n>1) tam.pop_back();
  58. 	sort(tam.begin(),tam.end(),cmp1);
  59. 	cout<<tam.size()<<endl;
  60. 	for (int i=0; i<=tam.size()-1; i++) cout<<tam[i].se<<" ";
  61. }
  62.  
Runtime error #stdin #stdout 0.04s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/NRVdY1
language:
C++14 (gcc 8.3)
created:
2 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!