fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  5. #define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
  6. #define fi first
  7. #define se second
  8. #define debug(x) cerr << " - " << #x << ": " << x << endl;
  9. #define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
  10. #define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
  11. #define sep() cerr << "--------------------" << endl;
  12. #define all(x) (x).begin(),(x).end()
  13. #define sz(x) (ll)x.size()
  14. #define ld long double
  15. #define ll long long
  16. #define int ll
  17. #define ii pair<int,int>
  18. #define v vector<int>
  19. #define vii vector<ii>
  20. #define vv vector<vector<int> >
  21. #define mp make_pair
  22. #define INF 1e14
  23. #define pb push_back
  24. #define EPS 1e-9
  25. const int MOD = 1000000007; // 998244353
  26. int xs[2002],ys[2002];
  27. int32_t main(){
  28. 	boost;
  29. 	//freopen(".in","r",stdin);
  30. 	int n;
  31. 	cin>>n;
  32. 	v vec;
  33. 	for (int i = 0; i < n; ++i){
  34. 		cin>>xs[i]>>ys[i];
  35. 		vec.pb(i);
  36. 	}
  37. 	int ans=0;
  38. 	while(!vec.empty()){
  39. 		ans++;
  40. 		int max_x=-INF,max_y=-INF,min_x=INF,min_y=INF;
  41. 		for(auto it:vec){
  42. 			max_x=max(max_x,xs[it]);
  43. 			max_y=max(max_y,ys[it]);
  44. 			min_x=min(min_x,xs[it]);
  45. 			min_y=min(min_y,ys[it]);
  46. 		}
  47. 		v n_vec;
  48. 		for(auto it:vec){
  49. 			if((xs[it]==min_x||xs[it]==max_x)&&(ys[it]<=max_y)&&(ys[it]>=min_y))continue;
  50. 			if((ys[it]==min_y||ys[it]==max_y)&&(xs[it]<=max_x)&&(xs[it]>=min_x))continue;
  51. 			n_vec.pb(it);
  52. 		}
  53. 		vec=n_vec;
  54. 	}
  55. 	cout<<ans;
  56. 	return 0;
  57. }
  58. //long long
  59. //array bounds
  60. //special cases
  61. //binary search
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
8
1 -1
2 -2
2 2
-1 1
-1 -1
-2 2
1 1
-2 -2
stdout
copy 
2
https://ideone.com/0zlUlT
language:
C++14 (gcc 8.3)
created:
4 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!