Cod sursa(job #2044003)

Utilizator KusikaPasa Corneliu Kusika Data 20 octombrie 2017 20:19:06
Problema Poligon Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>
using namespace std;

//Constants
const long long INF = std::numeric_limits<long long>::max();
const long long MOD = 1e9 + 7;
const long double PI = 3.141592653589793;

//MACROS
#define pb push_back
#define fi first
#define se second
#define rep(i, begin, end) for (int i = (begin); i < (end); i++)
#define per(i, begin, end) for (int i = (begin) - 1; i >= (end); i--)
typedef long long LL;
typedef pair <int,int> PII;

struct p{ int x, y; };

int sign(p p1, p p2, p p3) {
    long long det = 1LL * (p2.x - p1.x) * (p3.y - p1.y) - 1LL * (p3.x - p1.x) * (p2.y - p1.y);
    return (0 < det) - (det < 0);
}

bool intersect(int p1, int p2, int p3, int p4) {
    return max(min(p1,p2),min(p3,p4)) <= min(max(p1,p2),max(p3,p4));
}

int n, m, ans;
p pt[1000];

int main() {
    freopen("poligon.out","w",stdout);
	freopen("poligon.in","r",stdin);

	cin >> n >> m;
    rep(i,0,n) cin >> pt[i].x >> pt[i].y;
    rep(i,0,m) {
        p cur, lim;
        bool in = 0;
        cin >> cur.x >> cur.y;
        lim.x = -1, lim.y = cur.y;
        rep(j,0,n) {
            int nxt = (j+1)%n;
            if (intersect(pt[j].x,pt[nxt].x,cur.x,lim.x) && intersect(pt[j].y,pt[nxt].y,cur.y,lim.y)
                && (sign(cur,lim,pt[j]) * sign(cur,lim,pt[nxt]) <= 0)
                && (sign(pt[j],pt[nxt],cur) * sign(pt[j],pt[nxt],lim) <= 0)) in = !in;
        }
        ans += in;
    }
    cout << ans;
}