oj.uz

Submission #155629

# Submission time Handle Problem Language Result Execution time Memory
155629 2019-09-29T11:46:21 Z Akashi The Forest of Fangorn (CEOI14_fangorn) C++14
10 / 100
 589 ms 32764 KB 
#include <bits/stdc++.h>
using namespace std;

const double pi = 3.1415926535897;

int w, h;
int n, c, xG, yG;
int x[2005], y[2005], x2[10005], y2[10005];
double ang[10005];
vector <double> v[2005];
vector <int> sol;

inline double angle(double x, double y){
    double r = sqrt(x * x + y * y);

    x = x / r; y = y / r;

    double alpha = acos(x);
    if(y < 0) alpha = 2.0 * pi - alpha;
    return alpha;
}

inline bool check(int j, double alpha1, double alpha2){
    vector <double> :: iterator it = lower_bound(v[j].begin(), v[j].end(), alpha1);
    if(it == v[j].end()) return 1;
    if(*it <= alpha2) return 0;
    return 1;
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &w, &h);
    scanf("%d%d", &xG, &yG);

    scanf("%d", &c);
    for(int i = 1; i <= c ; ++i)
        scanf("%d%d", &x2[i], &y2[i]);

    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i) scanf("%d%d", &x[i], &y[i]);

    for(int i = 1; i <= n ; ++i){
        for(int j = i + 1; j <= n ; ++j){
            v[i].push_back(angle(x[i] - x[j], y[i] - y[j]));
            v[j].push_back(angle(x[j] - x[i], y[j] - y[i]));
        }
    }

    for(int i = 1; i <= n ; ++i) sort(v[i].begin(), v[i].end());

    for(int i = 1; i <= n ; ++i) ang[i] = angle(xG - x[i], yG - y[i]);

    for(int i = 1; i <= c ; ++i){
        bool ok = true;
        for(int j = 1; j <= n && ok ; ++j){
            double alpha1 = ang[j];
            double alpha2 = angle(x2[i] - x[j], y2[i] - y[j]);

            if(alpha1 > alpha2) swap(alpha1, alpha2);

            if(alpha2 - alpha1 <= pi) ok = check(j, alpha1, alpha2);
            else ok = min(check(j, 0.0, alpha1), check(j, alpha2, 2 * pi));
        }

        if(ok)
        sol.push_back(i);
    }

    printf("%d\n", sol.size());
    for(auto it : sol) printf("%d ", it);

    return 0;
}

Compilation message

fangorn.cpp: In function 'int main()':
fangorn.cpp:71:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type {aka long unsigned int}' [-Wformat=]
     printf("%d\n", sol.size());
                    ~~~~~~~~~~^
fangorn.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &w, &h);
     ~~~~~^~~~~~~~~~~~~~~~
fangorn.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &xG, &yG);
     ~~~~~^~~~~~~~~~~~~~~~~~
fangorn.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
     ~~~~~^~~~~~~~~~
fangorn.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x2[i], &y2[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fangorn.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
fangorn.cpp:42:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n ; ++i) scanf("%d%d", &x[i], &y[i]);
                                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 504 KB Output isn't correct
2 Correct 2 ms 452 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Correct 2 ms 376 KB Output is correct
5 Incorrect 2 ms 376 KB Output isn't correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Correct 3 ms 504 KB Output is correct
8 Incorrect 2 ms 504 KB Output isn't correct

Subtask #2
10.0 / 20.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 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 476 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Incorrect 2 ms 376 KB Output isn't correct
8 Incorrect 2 ms 376 KB Output isn't correct
9 Correct 2 ms 376 KB Output is correct
10 Incorrect 6 ms 760 KB Output isn't correct
11 Incorrect 6 ms 888 KB Output isn't correct
12 Correct 6 ms 888 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 589 ms 32764 KB Output isn't correct
2 Halted 0 ms 0 KB -