Submission #1240612

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240612		tvgk	별자리 (JOI12_constellation)	C++20	100 / 100	35 ms	8884 KiB

constellation

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 2e5 + 7, MOD = 1e9 + 7;

struct point
{
    ll x, y, tt;

    point operator- (const point& tmp)
    {
        x -= tmp.x;
        y -= tmp.y;
        return *this;
    }
};

int n, cnt[3];
point a[mxN];
vector<int> vt[3];

bool cross(point a, point b, point p)
{
    b = b - a;
    p = p - a;
    return (b.x * p.y - b.y * p.x) > 0;
}

bool cmp(point a, point b)
{
    return a.x < b.x;
}

vector<point> vc;
void Convex_Hull()
{
    sort(a + 1, a + n + 1, cmp);
    for (int dir = 0; dir <= 1; dir++)
    {
        for (int i = 1 + dir; i <= n; i++)
        {
            while (vc.size() > 1 && cross(vc[vc.size() - 2], vc.back(), a[i]))
                vc.pop_back();
            vc.push_back(a[i]);
        }
        reverse(a + 1, a + n + 1);
    }
    vc.pop_back();
}

ll pw(int j, int mx)
{
    if (!mx)
        return 1;

    ll res = pw(j, mx / 2);
    res = res * res % MOD;
    if (mx % 2)
        return res * j % MOD;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
//    freopen(task".INP", "r", stdin);
//    freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x >> a[i].y >> a[i].tt;
        cnt[a[i].tt]++;
    }

    Convex_Hull();

    int sz = vc.size();
    for (int i = 0; i < sz; i++)
    {
        if (!vc[i].tt)
            cnt[0]--;
        vc.push_back(vc[i]);

//        cout << vc[i].tt << " ";
    }

    vt[1].push_back(-1);
    vt[2].push_back(-1);
    for (int i = 0; i < vc.size(); i++)
        vt[vc[i].tt].push_back(i);
    vt[1].push_back(sz * 2);
    vt[2].push_back(sz * 2);

    ll ans = 0;
    for (int i = 0; i < sz; i++)
    {
        int r = lower_bound(vt[2].begin(), vt[2].end(), i) - vt[2].begin();
        r = min(i + sz - 1, vt[2][r]);

        int l = lower_bound(vt[1].begin(), vt[1].end(), i + sz) - vt[1].begin() - 1;
        l = max(i, vt[1][l]);

        if (r < l)
            continue;

        ans = (ans + r - l) % MOD;
    }
    ans = ans * pw(2, cnt[0]) % MOD;

    for (int i = 1; i <= 2; i++)
    {
        bool tmp = 0;
        for (int j = 0; j < sz; j++)
            tmp |= (vc[j].tt == i);

        if (!tmp)
            ans = (ans + pw(2, cnt[0]) - (!cnt[i])) % MOD;
    }

    cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10