Submission #1020267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020267		stefanopulos	Relay (COI16_relay)	C++17	18 / 100	2070 ms	3412 KiB

relay

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ldb;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ldb,ldb> pdd;

#define ff(i,a,b) for(int i = a; i <= b; i++)
#define fb(i,b,a) for(int i = b; i >= a; i--)
#define trav(a,x) for(auto& a : x)
 
#define sz(a) (int)(a).size()
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

const int mod = 1000000007;
const int inf = 1e9 + 5;
const int mxN = 200005;

struct point{
    int x, y;

    friend point operator-(point p, point q){
        point r = {p.x - q.x, p.y - q.y};
        return r;
    }

};


int n, m;
point A[mxN];
point P[mxN];

bool used[mxN];

int kvadrant(point p){
    if(p.x > 0 && p.y >= 0)return 0;
    if(p.x <= 0 && p.y > 0)return 1;
    if(p.x < 0 && p.y <= 0)return 2;
    if(p.x >= 0 && p.y < 0)return 3;
    return 0;
}

ll cross(int x1, int y1, int x2, int y2){
    return 1ll * x1 * y2 - 1ll * x2 * y1;
}

bool isBetween(point a, point b, point c){
    return cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y) == 0ll;
}

int orientation(point p, point q, point r) { 
    ll val = cross(r.x - q.x, r.y - q.y, q.x - p.x, q.y - p.y);
    if(val == 0)return 0;
    return (val > 0) ? 1 : 2; 
} 
  
bool intersect(point p1, point q1, point p2, point q2) { 
    int o1 = orientation(p1, q1, p2); 
    int o2 = orientation(p1, q1, q2); 
    int o3 = orientation(p2, q2, p1); 
    int o4 = orientation(p2, q2, q1); 

    if(o1 != o2 && o3 != o4){
        return !(isBetween(p1, q1, p2) || isBetween(p1, q1, q2));
    }

    return false; 
} 

bool check(point a, point b){    
    ff(i,2,m)if(intersect(a, b, P[1], P[i]) == 1)return 1;
    return 0;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n; ff(i,1,n)cin >> A[i].x >> A[i].y;
    cin >> m; ff(i,1,m)cin >> P[i].x >> P[i].y;

    point p = P[1];
    ff(i,1,m)if(P[i].y < p.y || (P[i].y == p.y && P[i].x < p.x))p = P[i];

    sort(P + 1, P + m + 1, [&](point s1, point s2){ 
        return kvadrant(s1 - p) == kvadrant(s2 - p) ? cross(s1.x - p.x, s1.y - p.y, s2.x - p.x, s2.y - p.y) > 0 : kvadrant(s1 - p) < kvadrant(s2 - p);
    });

    sort(A + 2, A + n + 1, [&](point s1, point s2){ 
        return kvadrant(s1 - A[1]) == kvadrant(s2 - A[1]) ? cross(s1.x - A[1].x, s1.y - A[1].y, s2.x - A[1].x, s2.y - A[1].y) > 0 : kvadrant(s1 - A[1]) < kvadrant(s2 - A[1]);
    });

    vector<int> vec; int br = 0;
    ff(i,2,n){
        if(check(A[1], A[i]) == 0){
            vec.pb(i); br += 1;
            used[i] = 1;
        }
    }

    ff(i,2,n){
        if(used[i] == 1)continue;

        for(auto c : vec){
            if(check(A[c], A[i]) == 0){
                br += 1;
                break;
            }
        }

    }

    cout << br << '\n';

    return 0;
}
/*



// probati bojenje sahovski
*/
 
 
 
 
 

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