Submission #233407

#	Time	Username	Problem	Language	Result	Execution time	Memory
233407		TempoTemp	Relay (COI16_relay)	C++14	0 / 100	6 ms	2816 KiB

relay

// Pinkie Pied!
#include<bits/stdc++.h>
#define x real()
#define y imag()
using namespace std;
typedef long double ld;
typedef complex < ld > point;
const int N = 300005;
int n, m, M[N], Mt[N], S[N];
point A[N], P[N];
pair < int , int > F[N];
mt19937 Rnd;//(time(0));
inline ld Cross(point a, point b)
{
    return (a.x * b.y - a.y * b.x);
}
inline bool CCW(point a, point b, point c)
{
    return (Cross(b - a, c - b) < 0);
}
inline bool OnRight(point p, int i)
{
    i = (i + n) % n;
    return (Cross(P[i + 1] - P[i], p - P[i]) <= 0);
}
inline bool Sees(point p, int i)
{
    return (OnRight(p, i));
    //return (OnRight(p, i) || OnRight(p, i - 1));
}
inline pair < int , int > GetIntv(point p)
{
    int pv = abs((int)Rnd()) % n;
    if (Cross(P[pv + 1] - P[pv], p - P[pv]) == 0)
        return (GetIntv(p));

    int le = pv + 1, ri = pv + n, md;
    while (ri - le > 1)
    {
        md = (le + ri) >> 1;
        if (CCW(p, P[pv], P[md]) == CCW(p, P[pv], P[pv + 1]))
            le = md;
        else
            ri = md;
    }

    auto Gett = [](point p, int l, int r)
    {
        if (!Sees(p, l) && !Sees(p, r))
            return make_pair(-1, -1);
        bool w = Sees(p, l);
        int le = l, ri = r, md;
        if (w) ri ++;
        while (ri - le > 1)
        {
            md = (le + ri) >> 1;
            if (Sees(p, md) == w)
                le = md;
            else
                ri = md;
        }
        if (w)
            return make_pair(l, le);
        return make_pair(ri, r);
    };

    if (ri == pv + n)
        return (GetIntv(p));

    pair < int , int > s1 = Gett(p, pv, le);
    pair < int , int > s2 = Gett(p, ri, pv + n);
    if (s1 == make_pair(-1, -1))
        return (s2);
    if (s2 == make_pair(-1, -1))
        return (s1);

    /*printf("%d ::: %d , %d\n", pv, le, ri);
    printf("(%d %d) : (%d %d)\n", s1.first, s1.second, s2.first, s2.second);*/
    if (s1.second + 1 == s2.first)
        return make_pair(s1.first, s2.second);
    assert(s1.first == pv && s2.second == pv + n);
    s1 = make_pair(s2.first, s1.second + n);
    if (s1.first >= n)
        s1.first -= n, s1.second -= n;
    return (s1);
}
int main()
{
    scanf("%d", &m);
    for (int i = 0; i < m; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        A[i] = point(a, b);
    }
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        P[i] = P[i + n] = P[i + n + n] = point(a, b);
    }

    /*for (int i = 0; i < 2; i ++)
        Rnd();

    pair < int , int > X;
    X = GetIntv(A[3 - 1]);

    printf("%d , %d\n", X.first, X.second);
    return 0;*/

    for (int i = 0; i < m; i ++)
    {
        F[i] = GetIntv(A[i]);
        if (F[i].first >= n)
            F[i].first -= n, F[i].second -= n;
        F[i].second ++;
        //printf("%d :: %d , %d\n", i + 1, F[i].first, F[i].second);
    }
    M[0] = 1;
    for (int w = 1; w <= 2; w ++)
    {
        memset(S, 0, sizeof(S));
        memset(Mt, 0, sizeof(Mt));
        for (int i = 0; i < m; i ++)
            if (M[i])
            {
                S[F[i].first + 1] ++;
                S[F[i].second + 1] --;
                S[F[i].first + 1 + n] ++;
                S[F[i].second + 1 + n] --;
            }
        for (int i = 1; i <= n + n + n; i ++)
            S[i] += S[i - 1];
        for (int i = 1; i <= n + n + n; i ++)
            S[i] = S[i - 1] + (S[i] > 0);
        for (int i = 0; i < m; i ++)
            if (!M[i])
            {
                if (S[F[i].second] - S[F[i].first])
                    Mt[i] = 1;
                if (S[F[i].second + n] - S[F[i].first + n])
                    Mt[i] = 1;
            }
        for (int i = 0; i < m; i ++)
            if (Mt[i]) M[i] = 1;
    }

    /*for (int i = 0; i < m; i ++)
        if (M[i]) printf("%d ", i + 1);
    printf("\n");*/

    int Cnt = 0;
    for (int i = 1; i < m; i ++)
        if (M[i]) Cnt ++;
    return !printf("%d\n", Cnt);
}

Compilation message (stderr)

relay.cpp: In function 'int main()':
relay.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
relay.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~
relay.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
relay.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 18
• Subtask 2: 0 / 19
• Subtask 3: 0 / 20
• Subtask 4: 0 / 43