Cod sursa(job #2177823)

Utilizator amaliarebAmalia Rebegea amaliareb Data 18 martie 2018 20:46:36
Problema Poligon Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <bits/stdc++.h>
#define Point complex<double>

using namespace std;
const double eps = 1e-9;
int n, m;
Point v[1005];

int sgn(double d) {
    if (abs(d) < eps) return 0;
    if (d < 0) return -1;
    return 1;
}

double ProdVect(Point a, Point b) {
    return (conj(a) * b).imag();
}

double ProdScal(Point a, Point b) {
    return (conj(a) * b).real();
}

bool OnSegm(Point a, Point b, Point p) {
    return sgn(ProdVect(p - a, p - b)) == 0 && sgn(ProdScal(p - a, p - b)) <= 0;
}

bool Intersect(Point a, Point b, Point p) {
    if (sgn(a.real() - b.real()) == 0) return 0;
    double y = (p.real() - a.real()) / (b.real() - a.real()) * (b.imag() - a.imag());
    if (sgn(y + a.imag() - p.imag()) < 0) return 0;
    if (a.real() > b.real()) swap(a, b);
    return sgn(b.real() - p.real()) >= 0 && sgn(p.real() - a.real()) > 0;
}

int main()
{
    ifstream cin("poligon.in");
    ofstream cout("poligon.out");
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        v[i] = {x, y};
    }
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
        int x, y;
        cin >> x >> y;
        Point p = {x, y};
        int cnt = 0;
        for (int j = 1; j <= n; ++j) {
            if (OnSegm(v[j], v[(j % n) + 1], p)) {
                ++ans;
                cnt = -1e9;
                break;
            }
            if (Intersect(v[j], v[(j % n) + 1], p)) ++cnt;
        }
        if (cnt >= 0){
            if (cnt % 2) ++ans;
        }
    }
    cout << ans << '\n';
    return 0;
}