# IOI '04 P1 - Artemis

Jul 23rd, 2022
1,122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4.
5. using namespace std;
6.
7. void compress(vector<int> &v) {
8.     vector<int> v2 = v;
9.     sort(v2.begin(), v2.end());
10.     // do not need to remove duplicates since there are no duplicates
11.     for (int &x : v) x = 1+lower_bound(v2.begin(), v2.end(), x)-v2.begin();
12. }
13.
14. struct Point {
15.     int x, y, id;
16.     bool operator < (const Point &p2) const {
17.         return pair<int, int>(x, y) < pair<int, int>(p2.x, p2.y);;
18.     }
19. };
20.
21. int main() {
22.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
23.     int n, t; cin >> n >> t;
24.     vector<int> x(n), y(n);
25.     for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
26.     compress(x);
27.     compress(y);
28.
29.     vector<Point> points(n);
30.     for (int i = 0; i < n; ++i) points[i].x = x[i], points[i].y = y[i], points[i].id = i+1;
31.     sort(points.begin(), points.end());
32.
33.     vector<int> treesDL(n); // trees down and left (excluding itself)
34.     for (int i = 0; i < n; ++i) {
35.         for (int j = 0; j < n; ++j) {
36.             if (points[j].x < points[i].x && points[j].y < points[i].y) ++treesDL[i];
37.         }
38.     }
39.
40.     int minTrees = n+1, bestI = 0, bestJ = 0;
41.     for (int i = 0; i < n && minTrees > t; ++i) { // fix one end tree
42.         int treesBelow = 0;
43.         vector<int> treesLeft(1+n); // number of trees at each y-value
44.         for (int j = 0; j < i; ++j) {
45.             if (points[j].y < points[i].y) ++treesBelow;
46.             ++treesLeft[points[j].y];
47.         }
48.         // convert treesLeft into prefix sums
49.         for (int yy = 1; yy <= n; ++yy) treesLeft[yy] += treesLeft[yy-1];
50.
51.         for (int j = i+1; j < n; ++j) {
52.             // find number of trees enclosed by trees i and j
53.             int trees;
54.             if (points[j].y > points[i].y) {
55.                 trees = treesDL[i] + treesDL[j] - treesBelow - treesLeft[points[j].y] + 1; // add tree i
56.             } else {
57.                 trees = treesBelow + treesLeft[points[j].y] - treesDL[i] - treesDL[j] + 2; // add trees i and j
58.             }
59.             if (trees >= t && trees < minTrees) minTrees = trees, bestI = points[i].id, bestJ = points[j].id;
60.
61.             if (points[j].y < points[i].y) ++treesBelow;
62.         }
63.     }
64.     cout << bestI << ' ' << bestJ << endl;
65.     return 0;
66. }