Guest User

Untitled

a guest
Jan 13th, 2018
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.14 KB | None | 0 0
  1. // IZI IZI
  2. // Real talk
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define sz(a) (int)a.size()
  8. #define all(x) (x).begin(),(x).end()
  9. #define vi vector <int>
  10. #define pb push_back
  11. #define mp make_pair
  12. #define ll long long
  13. #define sc scanf
  14. #define pf printf
  15. #define f first
  16. #define s second
  17. #define y1 dadssda
  18.  
  19. const int inf = (int)1e9;
  20. const int mod = inf + 7;
  21. const double pi = acos(-1.0);
  22. const double eps = 1e-9;
  23.  
  24. /*
  25. int bpow(int x, int e, int p) {
  26. if (e == 0) return 1;
  27. if (e % 2) return ((bpow(x, e - 1, p)) * (x)%p) % p;
  28. else {
  29. int k = bpow(x, e / 2, p);
  30. return ((k%p) * (k%p)) %p;
  31. }
  32. }
  33. int gcd(int a,int b) { return b?gcd(b,a%b):a;}
  34. */
  35.  
  36. const int days[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
  37. // /////////////////////////////////////////////////////////////////////
  38.  
  39.  
  40. int n;
  41. vector<pair<int, int> > ans;
  42. set<pair<int, int> > s;
  43.  
  44. bool ok(int l1, int r1, int l2, int r2){
  45. if(r1 <= l2 || r2 <= l1) return false;
  46. return true;
  47. }
  48. int main(){
  49. //freopen("in.in", "r", stdin);
  50. //freopen("out.out", "w", stdout);
  51. cin >> n;
  52. for(int i = 0, l, r; i < n; ++i){
  53. cin >> l >> r;
  54. s.insert(mp(min(l, r), max(l, r)));
  55. }
  56. while(true){
  57. set<pair<int ,int> > :: iterator it;
  58. int maxi = -inf;
  59. bool okei = 0;
  60. for (set <pair<int, int> > :: iterator i = s.begin(); i != s.end(); ++i ){
  61. int cnt = 0;
  62. int l1 = (*i).f;
  63. int r1 = (*i).s;
  64. for (set <pair<int, int> > :: iterator j = s.begin(); j != s.end(); ++j){
  65. if(j == i) continue;
  66. int l2 = (*j).f;
  67. int r2 = (*j).s;
  68. if(ok(l1, r1, l2, r2)){
  69. okei = 1;
  70. cnt++;
  71. }
  72. }
  73. if(cnt > maxi){
  74. maxi = cnt;
  75. it = i;
  76. }
  77. }
  78. if(okei == 0) break;
  79. int l = (*it).f;
  80. int r = (*it).s;
  81. s.erase(mp(l, r));
  82. }
  83. cout << sz(s) << endl;
  84. for (set <pair<int, int> > :: iterator i = s.begin(); i != s.end(); ++i ){
  85. cout << (*i).f << " " << (*i).s << endl;
  86. }
  87. return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment