Submission #1240559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240559		tvgk	별자리 (JOI12_constellation)	C++20	0 / 100	1 ms	328 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
{
    int 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();
}

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]);
    }

    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;
    if (!cnt[1] && !cnt[2])
        ans = vc.size() * (vc.size() - 1) % MOD;
    else
    {
        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, 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 += r - l;
        }
        if (vt[2].size() == 2)
            ans -= sz - (cnt[2] != 0);
        if (vt[1].size() == 2)
            ans += (cnt[1] != 0);
    }

    for (int i = 1; i <= cnt[0]; i++)
        ans = ans * 2 % MOD;
    cout << ans;
}

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