Submission #155629

#	Time	Username	Problem	Language	Result	Execution time	Memory
155629		Akashi	The Forest of Fangorn (CEOI14_fangorn)	C++14	10 / 100	589 ms	32764 KiB

fangorn

#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 (stderr)

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 / 30
• Subtask 2: 10 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 20