SHARE
TWEET

Untitled

a guest Aug 18th, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define optimize ios::sync_with_stdio(false); cin.tie(NULL)
  3. #define pii pair<int, int>
  4. #define MAXN 2020
  5.  
  6. using namespace std;
  7.  
  8. pii pontos[MAXN];
  9.  
  10. bool ok[MAXN][MAXN];
  11. int N;
  12. map<pii, bool> mapa;
  13.  
  14. void precalc()
  15. {
  16.     for(int i = 0; i < N; i++)
  17.     {
  18.         for(int j = i + 1; j < N; j++)
  19.         {
  20.             int x1 = pontos[i].first, y1 = pontos[i].second;
  21.             int x2 = pontos[j].first, y2 = pontos[j].second;
  22.  
  23.             if(x1 != x2 && y1 != y2 && mapa[pii(x1, y2)] && mapa[pii(x2, y1)])
  24.                 // cout << x1 << " " << y1 << endl << x1 << " " << y2 << endl << x2 << " " << y2 << endl << x2 << " " << y1 << endl << endl;
  25.                 ok[i][j] = true;
  26.         }
  27.     }
  28. }
  29.  
  30. int dp[MAXN];
  31.  
  32. int solve(int i)
  33. {
  34.     if(dp[i] != -1) return dp[i];
  35.     if(i == N) return dp[N] = 0;
  36.  
  37.     int best = 0;
  38.  
  39.     for(int j = i + 1; j < N; j++)
  40.         if(ok[i][j])
  41.             best = max(best, 1 + solve(j));
  42.  
  43.     return dp[i] = best;
  44. }
  45.  
  46. int main(int argc, char** argv)
  47. {
  48.     optimize;
  49.  
  50.     memset(dp, -1, sizeof dp);
  51.  
  52.     cin >> N;
  53.  
  54.     for(int i = 0; i < N; i++)
  55.     {
  56.         cin >> pontos[i].first >> pontos[i].second;
  57.         mapa[pii(pontos[i].first, pontos[i].second)] = true;
  58.     }
  59.  
  60.     sort(pontos, pontos + N);
  61.  
  62.     precalc();
  63.  
  64.     cout << solve(0) << endl;
  65.  
  66.     return 0;
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top