제출 #229419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229419		VEGAnn	Zvijezda (COCI19_zvijezda)	C++14	50 / 110	229 ms	7076 KiB

zvijezda

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 100100;
int n, x[N], y[N], T;

bool cw(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3){
    return (x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3) < 0;
}

bool get(int id, ld x3, ld y3){
    int nt = (id + 1);
    if (nt == n) nt = 0;

    return !cw(x[id], y[id], x[nt], y[nt], x3, y3);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif // _LOCAL

    cin >> T >> n;

    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i];

    int qq; cin >> qq;

    int p1 = 0, p2 = n / 2;

    for (; qq; qq--){
        ld cx, cy; cin >> cx >> cy;

        bool fi = get(p1, cx, cy);
        bool se = get(p2, cx, cy);

        if (fi && se){
            cout << "DA\n";
        } else if (!fi && !se){
            cout << "NE\n";
        } else {
            if (!fi) swap(p1, p2);

            int l1 = 1, r1 = n / 2;
            while (l1 < r1){
                int md = (l1 + r1 + 1) >> 1;

                if (get((p1 - md + 1 + n) % n, cx, cy))
                    l1 = md;
                else r1 = md - 1;
            }

            int l2 = 1, r2 = n / 2;
            while (l2 < r2){
                int md = (l2 + r2 + 1) >> 1;

                if (get((p1 + md - 1) % n, cx, cy))
                    l2 = md;
                else r2 = md - 1;
            }

            if ((l1 + l2 - 1) > n / 2)
                cout << "DA\n";
            else cout << "NE\n";
        }
    }

    // check __int128

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 60