• API
• FAQ
• Tools
• Archive
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.

Top