oj.uz

Submission #365063

# Submission time Handle Problem Language Result Execution time Memory
365063 2021-02-10T20:37:36 Z ijxjdjd The Forest of Fangorn (CEOI14_fangorn) C++14
100 / 100
 715 ms 844 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

int N, M;
const int MAXN = 2000;
const int MAXM = 10000;
struct Point {
    ll x, y;
    void print() {
        cerr << x << " " << y << endl;
    }
};
Point start;
int bad[MAXM];
Point pos[MAXN];
Point cmps[MAXM];
void solve(int n) {
    FR(i, N) {
        if (i != n) {
            pos[i].x -= pos[n].x;
            pos[i].y -= pos[n].y;
        }
    }
    FR(i, M) {
        cmps[i].x -= pos[n].x;
        cmps[i].y -= pos[n].y;
    }
    start.x -= pos[n].x;
    start.y -= pos[n].y;
    vector<Point> pt;
    FR(i, N) {
        if (i != n) {
            pt.push_back({-pos[i].x, -pos[i].y});
        }
    }
    auto comp = [](const auto& lhs, const auto& rhs) {
        if (lhs.x == 0) {
            if (lhs.y > 0) {
                return true;
            }
            else {
                return rhs.x < 0;
            }
        }
        if (rhs.x == 0) {
            if (rhs.y > 0) {
                return false;
            }
            else {
                return lhs.x >= 0;
            }
        }
        if (lhs.x < 0 && rhs.x > 0) {
            return false;
        }
        if (lhs.x > 0 && rhs.x < 0) {
            return true;
        }
        if (lhs.x > 0) {
            return lhs.y * rhs.x - lhs.x * rhs.y > 0;
        }
        else {
            return lhs.y * (-rhs.x) - (-lhs.x) * rhs.y < 0;
        }
    };
    sort(all(pt), comp);
//    cout << n << endl;
//    for (auto& p : pt) {
//        p.print();
//    }
    if (comp(start, pt[0]) || comp(pt[pt.size()-1], start)) {
        FR(i, M) {
            if (comp(cmps[i], pt[0]) || comp(pt[pt.size()-1], cmps[i])) {
                bad[i]++;
            }
        }
    }
    else {
        for (int i = 1; i < pt.size(); i++) {
            if (comp(start, pt[i])) {
                FR(j, M) {
                    if (!comp(cmps[j], pt[i-1]) && comp(cmps[j], pt[i])) {
                        bad[j]++;
                    }
                }
                break;
            }
        }
    }
    FR(i, N) {
        if (i != n) {
            pos[i].x += pos[n].x;
            pos[i].y += pos[n].y;
        }
    }
    FR(i, M) {
        cmps[i].x += pos[n].x;
        cmps[i].y += pos[n].y;
    }
    start.x += pos[n].x;
    start.y += pos[n].y;
}
int main() {
//    freopen("input.in", "r", stdin);
	cin.tie(0);
	cin.sync_with_stdio(0);
	int hg;
	cin >> hg >> hg;
	cin >> start.x >> start.y;
	cin >> M;
	FR(i, M) {
	    cin >> cmps[i].x >> cmps[i].y;
	}
	cin >> N;
	FR(i, N) {
        cin >> pos[i].x >> pos[i].y;
	}
    FR(i, N) {
        solve(i);
    }
    vector<int> ans;
    FR(j, M) {
        if (bad[j] == N) {
            ans.push_back(j+1);
        }
    }
    cout << ans.size() << '\n';
    for (int p :ans){
        cout << p << " ";
    }
	return 0;
}

Compilation message

fangorn.cpp: In function 'void solve(int)':
fangorn.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 1; i < pt.size(); i++) {
      |                         ~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 3 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 364 KB Output is correct
11 Correct 4 ms 364 KB Output is correct
12 Correct 4 ms 364 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 120 ms 364 KB Output is correct
5 Correct 28 ms 364 KB Output is correct
6 Correct 463 ms 492 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 472 ms 620 KB Output is correct
2 Correct 585 ms 844 KB Output is correct
3 Correct 679 ms 836 KB Output is correct
4 Correct 715 ms 812 KB Output is correct