Submission #155633

#	Time	Username	Problem	Language	Result	Execution time	Memory
155633		Akashi	The Forest of Fangorn (CEOI14_fangorn)	C++14	80 / 100	3043 ms	65400 KiB

fangorn

#include <bits/stdc++.h>
using namespace std;

const long double pi = 3.14159265358979323846;

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

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

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

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

inline bool check(int j, long double alpha1, long double alpha2){
    vector <long 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){
            long double alpha1 = ang[j];
            long double alpha2 = angle(x2[i] - x[j], y2[i] - y[j]);

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

            ok = max(min(check(j, 0.0, alpha1), check(j, alpha2, 2 * pi)), check(j, alpha1, alpha2));
        }

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