oj.uz

Submission #52250

# Submission time Handle Problem Language Result Execution time Memory
52250 2018-06-25T06:26:36 Z Alexa2001 The Forest of Fangorn (CEOI14_fangorn) C++17
50 / 100
 3000 ms 1044 KB 
#include <bits/stdc++.h>

using namespace std;

const int Qmax = 10005, Nmax = 2005;
const double PI = acos(-1);

int Lines, Rows, L, C, N, Q, p, i, j, ans;
bool good[Qmax];

struct point
{
    int x, y;
    point operator - (const point &other) const
    {
        return {x - other.x, y - other.y};
    }
};
vector<point> A;
point a[Nmax], S, q[Qmax];

bool cmp(point a, point b)
{
    double p1 = atan2(a.y, a.x), p2 = atan2(b.y, b.x);
    if(p1 < 0) p1 += 2*PI;
    if(p2 < 0) p2 += 2*PI;
    return p1 < p2;
}

int Find(point P)
{
    int st = 0, dr = A.size() - 1, mid;

    while(st <= dr)
    {
        mid = (st+dr) / 2;
        if(cmp(P, A[mid])) dr = mid-1;
            else st = mid+1;
    }

    return st % A.size();
}

int main()
{
  //  freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    cin >> Lines >> Rows >> S.x >> S.y;

    cin >> Q;
    for(i=1; i<=Q; ++i) cin >> q[i].x >> q[i].y, good[i] = 1;

    cin >> N;
    for(i=1; i<=N; ++i) cin >> a[i].x >> a[i].y;

    ans = Q;
    for(i=1; i<=N; ++i)
    {
        A.clear();

        for(j=1; j<=N; ++j)
            if(i != j) A.push_back(a[i] - a[j]);

        sort(A.begin(), A.end(), cmp);

        p = Find(S - a[i]);

        for(j=1; j<=Q; ++j)
            if(good[j] && Find(q[j] - a[i]) != p) good[j] = 0, --ans;
    }

    cout << ans << '\n';
    for(i=1; i<=Q; ++i)
        if(good[i]) cout << i << ' ';

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 624 KB Output is correct
7 Correct 6 ms 648 KB Output is correct
8 Correct 5 ms 652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 656 KB Output is correct
2 Correct 4 ms 680 KB Output is correct
3 Correct 6 ms 688 KB Output is correct
4 Correct 7 ms 780 KB Output is correct
5 Correct 7 ms 892 KB Output is correct
6 Correct 17 ms 892 KB Output is correct
7 Correct 2 ms 892 KB Output is correct
8 Correct 2 ms 892 KB Output is correct
9 Correct 6 ms 892 KB Output is correct
10 Correct 35 ms 892 KB Output is correct
11 Correct 28 ms 892 KB Output is correct
12 Correct 46 ms 892 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 892 KB Output is correct
2 Correct 3 ms 892 KB Output is correct
3 Correct 5 ms 892 KB Output is correct
4 Correct 1256 ms 956 KB Output is correct
5 Correct 235 ms 956 KB Output is correct
6 Execution timed out 3065 ms 956 KB Time limit exceeded

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 1044 KB Time limit exceeded
2 Halted 0 ms 0 KB -