Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- void compress(vector<int> &v) {
- vector<int> v2 = v;
- sort(v2.begin(), v2.end());
- // do not need to remove duplicates since there are no duplicates
- for (int &x : v) x = 1+lower_bound(v2.begin(), v2.end(), x)-v2.begin();
- }
- struct Point {
- int x, y, id;
- bool operator < (const Point &p2) const {
- return pair<int, int>(x, y) < pair<int, int>(p2.x, p2.y);;
- }
- };
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int n, t; cin >> n >> t;
- vector<int> x(n), y(n);
- for (int i = 0; i < n; ++i) cin >> x[i] >> y[i];
- compress(x);
- compress(y);
- vector<Point> points(n);
- for (int i = 0; i < n; ++i) points[i].x = x[i], points[i].y = y[i], points[i].id = i+1;
- sort(points.begin(), points.end());
- vector<int> treesDL(n); // trees down and left (excluding itself)
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- if (points[j].x < points[i].x && points[j].y < points[i].y) ++treesDL[i];
- }
- }
- int minTrees = n+1, bestI = 0, bestJ = 0;
- for (int i = 0; i < n && minTrees > t; ++i) { // fix one end tree
- int treesBelow = 0;
- vector<int> treesLeft(1+n); // number of trees at each y-value
- for (int j = 0; j < i; ++j) {
- if (points[j].y < points[i].y) ++treesBelow;
- ++treesLeft[points[j].y];
- }
- // convert treesLeft into prefix sums
- for (int yy = 1; yy <= n; ++yy) treesLeft[yy] += treesLeft[yy-1];
- for (int j = i+1; j < n; ++j) {
- // find number of trees enclosed by trees i and j
- int trees;
- if (points[j].y > points[i].y) {
- trees = treesDL[i] + treesDL[j] - treesBelow - treesLeft[points[j].y] + 1; // add tree i
- } else {
- trees = treesBelow + treesLeft[points[j].y] - treesDL[i] - treesDL[j] + 2; // add trees i and j
- }
- if (trees >= t && trees < minTrees) minTrees = trees, bestI = points[i].id, bestJ = points[j].id;
- if (points[j].y < points[i].y) ++treesBelow;
- }
- }
- cout << bestI << ' ' << bestJ << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement