Submission #963527

#	Time	Username	Problem	Language	Result	Execution time	Memory
963527		ttttttttttttth	Zvijezda (COCI19_zvijezda)	C++17	0 / 110	1040 ms	3940 KiB

zvijezda

// Author: Ivan Teo
// Created: Mon Apr 15 14:41:22 2024

#define TASKNAME "tomau"
#include <bits/stdc++.h>
using namespace std;

#define fore(i, a, b) for (int i = (a); i <= (b); i++)
#define int long long
using vi = vector<int>;
using ii = pair<int, int>;
#define pb emplace_back
#define fi first
#define se second
#define sz(v) ((int)v.size())
#define all(v) v.begin() + 1, v.end()
#define alll(v) v.begin(), v.end()
#define db(x) cerr << "[" << #x << " = " << x << "]"
#define el cerr << "\n=============================\n"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r)
{
    assert(l <= r);
    return uniform_int_distribution<int> (l, r)(rng);
}

typedef struct Vector
{
    int x, y;
    Vector operator - (const Vector &o) const
    {
        return {x - o.x, y - o.y};
    }
    int cross (const Vector &o)
    {
        if  ((__int128) x * o.y == (__int128) y * o.x) return 0;
        if  ((__int128) x * o.y < (__int128) y * o.x) return -1;
        return 1;
    }
} point;
int direc(point a, point b, point c)
{
    Vector x = b - a;
    Vector y = c - b;
    return x.cross(y);
}
bool ccw (point a, point b, point c)
{
    return direc(a, b, c) > 0;
}
bool cw (point a, point b, point c)
{
    return direc(a, b, c) < 0;
}

const int maxn = 1e5 + 5;
int n;
point a[maxn];
bool in (point b)
{
    int l = 2, r = n;
    if (l == 2 && !ccw(a[1], a[2], b)) return 0;
    if (r == n && !ccw (a[n], a[1], b)) return 0;
    while (r - l > 1)
    {
        int mid = (r + l) >> 1;
        if (direc(a[1], a[mid], b) >= 0) l = mid;
        else r = mid;
    }
    return ccw (a[l], a[r], b);
}

int next(int i)
{
    if (i == n - 1) return n;
    return (i + 1) % n;
}

int dx(int i)
{
    i = i + n / 2;
    i %= n;
    if (i == 0) return n;
    return i;
}

bool check(point b)
{
    if (in(b)) return 1;
    int l = 2, r = n;
    fore(i, 1, n)
    {
        if (ccw(b, a[i], a[next(i)]) && ccw(b, a[dx(i)], a[dx(next(i))]))
            return 1;
    }
    return 0;
}
void solve()
{
    int t;
    cin >> t;
    cin >> n;
    fore(i, 1, n) cin >> a[i].x >> a[i].y;
    int p = 0;
    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        int x = (u ^ (t * p * p * p));
        int y = (v ^ (t * p * p * p));
        bool flag = check({x, y});
        if (flag) cout << "YES\n";
        else cout << "NO\n";
        p += flag;
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    if (fopen("in", "r"))
        freopen("in", "r", stdin);
    if (fopen(TASKNAME ".inp", "r"))
        freopen(TASKNAME ".inp", "r", stdin),
                freopen(TASKNAME ".out", "w", stdout);
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
    return 0;
}

Compilation message (stderr)

zvijezda.cpp: In function 'bool check(point)':
zvijezda.cpp:90:9: warning: unused variable 'l' [-Wunused-variable]
   90 |     int l = 2, r = n;
      |         ^
zvijezda.cpp:90:16: warning: unused variable 'r' [-Wunused-variable]
   90 |     int l = 2, r = n;
      |                ^
zvijezda.cpp: In function 'int main()':
zvijezda.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen("in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
zvijezda.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(TASKNAME ".inp", "r", stdin),
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
zvijezda.cpp:127:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                 freopen(TASKNAME ".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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