Submission #43754

#	Time	Username	Problem	Language	Result	Execution time	Memory
43754		chpipis	The Forest of Fangorn (CEOI14_fangorn)	C++11	100 / 100	1568 ms	33708 KiB

fangorn

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rep(i, s, e) for (int i = s; i < e; i++)

// START for segment tree
#define params int p, int L, int R
#define housekeep int mid = (L + R) >> 1, left = p << 1, right = left | 1
// END

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAX_N = 2e3 + 5;
const int MAX_C = 1e4 + 5;

inline ll cross(ii a, ii b) {
    return a.fi * 1LL * b.se - a.se * 1LL * b.fi;
}

bool comp(vii vec) {
    for (int i = 0; i < 3; i++) {
        int nxt = (i + 1) % 3;
        int prv = (i + 3 - 1) % 3;
        if (cross(vec[i], vec[nxt]) > 0 && cross(vec[prv], vec[i]) > 0)
            return true;
    }
    return false;
}

ii tree[MAX_N], camp[MAX_C];
vii vec[MAX_N];
ii best[MAX_N][2];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    int w, h;
    scanf("%d %d", &w, &h);
    ii gimli;
    scanf("%d %d", &gimli.fi, &gimli.se);
    int c;
    scanf("%d", &c);
    for (int i = 1; i <= c; i++) {
        scanf("%d %d", &camp[i].fi, &camp[i].se);
    }
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &tree[i].fi, &tree[i].se);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            ii point = tree[j];
            point.fi -= tree[i].fi;
            point.se -= tree[i].se;
            point.fi *= -1;
            point.se *= -1;
            vec[i].pb(point);
        }
    }
    for (int i = 1; i <= n; i++) {
        best[i][0] = best[i][1] = vec[i][0];
        for (int j = 1; j < (int)vec[i].size(); j++) {
            ii cur = vec[i][j];
            ii gnow = gimli;
            gnow.fi -= tree[i].fi;
            gnow.se -= tree[i].se;
            if (comp((vii){gnow, best[i][0], cur}))
                best[i][0] = cur;
            if (comp((vii){gnow, cur, best[i][1]}))
                best[i][1] = cur;
        }
    }
    vi ans;
    for (int i = 1; i <= c; i++) {
        bool found = true;
        for (int j = 1; j <= n; j++) {
            ii cur = camp[i];
            cur.fi -= tree[j].fi;
            cur.se -= tree[j].se;
            if (!comp((vii){best[j][0], cur, best[j][1]}))
                found = false;
        }
        if (found) ans.pb(i);
    }
    printf("%d\n", (int)ans.size());
    for (auto it : ans)
        printf("%d ", it);
    puts("");
    return 0;
}

Compilation message (stderr)

fangorn.cpp: In function 'int main()':
fangorn.cpp:82:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &w, &h);
                           ^
fangorn.cpp:84:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &gimli.fi, &gimli.se);
                                         ^
fangorn.cpp:86:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
                    ^
fangorn.cpp:88:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &camp[i].fi, &camp[i].se);
                                                 ^
fangorn.cpp:91:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
fangorn.cpp:93:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &tree[i].fi, &tree[i].se);
                                                 ^

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 20 / 20