Cod sursa(job #2132770)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 16 februarie 2018 00:22:29
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.89 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream fi("poligon.in");
ofstream fo("poligon.out");
 
using f64 = double;
 
const f64 C = cos(1.3241), S = sin(1.3241), EPS = 1e-7;
const int N = 805;
 
struct Ptx {
    f64 x, y;
 
    Ptx rot() {
        f64 nx = x * C + y * S, ny = y * C - x * S;
        x = nx, y = ny;
        return *this; }
 
    inline bool operator < (const Ptx &arg) const {
        return x < arg.x; }
 
    inline bool operator > (const Ptx &arg) const {
        return x > arg.x; }
 
    inline bool operator == (const Ptx &arg) const {
        return abs(x - arg.x) < EPS && abs(y - arg.y) < EPS; } };
 
struct Seg {
    f64 a, b;
 
    inline Seg() { }
    inline Seg(const Ptx &v, const Ptx &w) {
        a = (v.y - w.y) / (v.x - w.x);
        b = v.y - a * v.x; }
 
    inline f64 operator [] (const f64 &x) const {
        return x * a + b; }
    inline bool operator < (const Ptx &arg) const {
        return arg.y > arg.x * a + b; }
    inline bool operator > (const Ptx &arg) const {
        return arg.y < arg.x * a + b; }
    inline bool operator == (const Ptx &arg) const {
        return abs(arg.y - (arg.x * a + b)) < EPS; } };
 
vector<Seg> str[N];
vector<Ptx> pts;
vector<int> srt;
int n, m;
 
void get_strips() {
    Ptx x, y;
 
    srt.resize(n);
    iota(begin(srt), end(srt), 0);
    sort(begin(srt), end(srt), [pts](int a, int b) {
        return pts[a] < pts[b]; });
 
    for (int i = 1; i < n; ++i) {
        x = pts[srt[i - 1]];
        y = pts[srt[i]];
        for (int j = 0; j < n; ++j)
            if (min(pts[j], pts[(j + 1) % n]).x - EPS < x.x && y.x < max(pts[j], pts[(j + 1) % n]).x + EPS)
                str[i].emplace_back(pts[j], pts[(j + 1) % n]);
 
        sort(begin(str[i]), end(str[i]), [x = pts[srt[i - 1]].x, px = pts[srt[i]].x](const Seg &a, const Seg &b) {
            return (abs(a[x] - b[x]) < EPS) ? (a[px] < b[px]) : (a[x] < b[x]); }); } }
 
bool in(Ptx arg) {
    int strip = -1, line = -1;
 
    if (arg < pts[srt.front()])
        return false;
    if (arg > pts[srt.back()])
        return false;
 
    for (int msk = 1 << 10; msk; msk>>= 1)
        if (strip + msk < n && pts[srt[strip + msk]].x < arg.x)
            strip+= msk;
    ++strip;
 
    for (int msk = 1 << 10; msk; msk>>= 1)
        if (line + msk < str[strip].size() && str[strip][line + msk] < arg)
            line+= msk;
 
    if (line % 2 == 0)
        return true;
 
    if (line >= 0 && str[strip][line] == arg)
        return true;
    if (line + 1 < str[strip].size() && str[strip][line + 1] == arg)
        return true;
 
    return false; }
 
int main() {
    int ant = 0;
    Ptx p;
 
    fi >> n >> m;
 
    pts.resize(n);
    for (auto &i: pts) {
        fi >> i.x >> i.y;
        i.x+= 1.0, i.y+= 1.0;
        i.rot(); }
 
    get_strips();
 
    while (m--) {
        fi >> p.x >> p.y;
        p.x+= 1.0, p.y+= 1.0;
        ant+= in(p.rot()) ? 1 : 0; }
 
    fo << ant << '\n';
 
    return 0; }