Submission #1060439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060439		Thanhs	Kućice (COCI21_kucice)	C++14	110 / 110	67 ms	2908 KiB

Main

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 2e5 + 5;
const int mod = 1e9 + 7;

struct mi
{
    int v;
    mi() : v(0){}
    mi(int _v) : v(_v)
    {
        if (v >= mod)
            v -= mod;
    }
    mi operator+(const mi& o)
    {
        return mi(v + o.v);
    }
    mi operator-(const mi& o)
    {
        return mi(v + mod - o.v);
    }
    mi operator*(const mi& o)
    {
        return mi(1ll * v * o.v % mod);
    }
    mi& operator+=(const mi &o)
    {
        v += o.v;
        if (v >= mod)
            v -= mod;
        return *this;
    }
    mi& operator-=(const mi &o)
    {
        v += mod - o.v;
        if (v >= mod)
            v -= mod;
        return *this;
    }
    mi& operator*=(const mi& o)
    {
        v = 1ll * v * o.v % mod;
        return *this;
    }
};

struct Pt
{
    int x, y;
    Pt(){}
    Pt(int x, int y) : x(x), y(y){}
}pt[NM];

int cw(Pt a, Pt b, Pt c)
{
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y) < 0;
}

vector<Pt> v[2];
mi ex[NM], ans;
int n;

void calc(int x)
{
    v[0].clear(); v[1].clear();
    for (int i = 1; i <= n; i++)
        if (i != x)
            v[pt[i].x > pt[x].x].push_back(pt[i]);
    for (int i = 0; i < 2; i++)
        sort(v[i].begin(), v[i].end(), [&](const Pt& a, const Pt& b) {return cw(pt[x], a, b);});
    for (auto t : v[1])
        v[0].push_back(t);
    int m = v[0].size();
    int j = 0, cnt = 0;
    for (int i = 0; i < m; i++)
    {
        if (cnt == -1)
        {
            j = i;
            cnt = 0;
        }
        while ((j + 1) % m != i && !cw(v[0][i], pt[x], v[0][(j + 1) % m]))
        {
            j = (j + 1) % m;
            cnt++;
        }
        ans += ex[cnt];
        cnt--;
    }
}

void solve()
{
    cin >> n;
    ex[0].v = 1;
    for (int i = 1; i <= n; i++)
        ex[i] = ex[i - 1] * mi(2);
    for (int i = 1; i <= n; i++)
        cin >> pt[i].x >> pt[i].y;
    for (int i = 1; i <= n; i++)
        calc(i);
    ans += mi(n);
    cout << (mi(n) * ex[n] - ans).v;
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int tc = 1;
    // cin >> tc;
    while (tc--)
        solve();
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 30 / 30
• Subtask 5: 30 / 30