Submission #1020107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020107		stefanopulos	Relay (COI16_relay)	C++17	18 / 100	2045 ms	4920 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;
};

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

bool used[mxN];

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 cross(s1.x - p.x, s1.y - p.y, s2.x - p.x, s2.y - p.y) > 0;
    });

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

    }

    for(auto c : vec){

        ff(i,2,n){
            if(!used[i] && check(A[c], A[i]) == 0){
                br += 1; used[i] = 1;
            }
        }

    }

    cout << br << '\n';

    return 0;
}
/*



// probati bojenje sahovski
*/
 
 
 
 
 

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