Submission #560926

#	Time	Username	Problem	Language	Result	Execution time	Memory
560926		Yazan_Alattar	Relay (COI16_relay)	C++14	0 / 100	37 ms	340 KiB

relay

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 5007;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

struct point{
    ll x, y;
    void read(){
        cin >> x >> y;
        return;
    }

    bool collinear(point a, point b)
    {
        a.x -= (*this).x;
        a.y -= (*this).y;
        b.x -= (*this).x;
        b.y -= (*this).y;
        return (a.x * b.y - a.y * b.x == 0);
    }

};

point sub(point a, point b){return {a.x - b.x, a.y - b.y};}
ll cross(point a, point b){return (a.x * b.y - b.x * a.y);}

bool intersect(point p1, point p2, point p3, point p4)
{
    if(cross(sub(p2, p1), sub(p4, p3)) == 0){
        if(cross(sub(p2, p1), sub(p4, p1)) != 0) return 0;
        for(int i = 0; i < 2; ++i){
            if(max(p1.x, p2.x) < min(p3.x, p4.x) || max(p1.y, p2.y) < min(p3.y, p4.y)) return 0;
            swap(p1, p4);
            swap(p1, p4);
        }

    }
    else for(int i = 0; i < 2; ++i){
        if((cross(sub(p2, p1), sub(p3, p1)) < 0 && cross(sub(p2, p1), sub(p4, p1)) < 0) || (cross(sub(p2, p1), sub(p3, p1)) > 0 && cross(sub(p2, p1), sub(p4, p1)) > 0)) return 0;
        swap(p1, p3);
        swap(p2, p4);
    }
    return 1;
}

queue <int> q;
point p[M], pol[M];
int n, m;
bool vist[M];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; ++i) p[i].read();

    cin >> m;
    for(int i = 1; i <= m; ++i) pol[i].read();

    vist[1] = 1;
    for(int i = 2; i <= n; ++i){
        bool ok = 1;
        for(int j = 1; j <= m; ++j)
            if(intersect(p[1], p[i], pol[j], pol[(j % m) + 1])) ok = 0;

        if(ok){
            vist[i] = 1;
            q.push(i);
        }
    }

    while(!q.empty()){
        int node = q.front();
        q.pop();

        for(int i = 1; i <= n; ++i) if(i != node){
            bool ok = 1;
            for(int j = 1; j <= m; ++j)
                if(intersect(p[node], p[i], pol[j], pol[(j % m) + 1])) ok = 0;

            if(ok) vist[i] = 1;
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i) ans += vist[i];
    cout << ans << endl;
    return 0;
}

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