oj.uz

답안 #711745

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711745 2023-03-17T11:57:19 Z becaido Zvijezda (COCI19_zvijezda) C++17
20 / 110
 1000 ms 4432 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define int long long

using i128 = __int128;

using point = pair<int, int>;

const int SIZE = 1e5 + 5;

int subtask, n, q;
point p[SIZE];

i128 cross(point a, point b) {
    return (i128) a.F * b.S - (i128) a.S * b.F;
}

point operator - (point a, point b) {
    return point(a.F - b.F, a.S - b.S);
}

void solve() {
    cin >> subtask >> n;
    FOR (i, 1, n) cin >> p[i].F >> p[i].S;
    cin >> q;
    while (q--) {
        point P;
        cin >> P.F >> P.S;
        bool f = 0;
        FOR (i, 1, n / 2) {
            auto p1 = p[i], p2 = p[i + 1];
            auto p3 = p[i + n / 2], p4 = p[i + n / 2 + 1 > n ? 1 : i + n / 2 + 1];
            if (cross(p1 - P, p2 - P) > 0 && cross(p3 - P, p4 - P) > 0) {
                f = 1;
                break;
            }
        }
        cout << (f ? "DA" : "NE") << '\n';
    }
}

int32_t main() {
    Waimai;
    solve();
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 8 ms 488 KB Output is correct
9 Correct 7 ms 476 KB Output is correct
10 Correct 8 ms 468 KB Output is correct
11 Correct 9 ms 480 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 8 ms 468 KB Output is correct
8 Correct 8 ms 488 KB Output is correct
9 Correct 7 ms 476 KB Output is correct
10 Correct 8 ms 468 KB Output is correct
11 Correct 9 ms 480 KB Output is correct
12 Correct 80 ms 4432 KB Output is correct
13 Correct 225 ms 4416 KB Output is correct
14 Execution timed out 1059 ms 3792 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 2044 KB Time limit exceeded
2 Halted 0 ms 0 KB -