Cod sursa(job #3148750)

Utilizator andiRTanasescu Andrei-Rares andiR Data 3 septembrie 2023 23:41:42
Problema Poligon Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <stdlib.h>
#include <time.h>

#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;
ifstream fin ("poligon.in");
ofstream fout ("poligon.out");
typedef long long ll;
const ll Nmax=800, inf=60000;
using pll=pair<ll, ll>;
struct point{
    ll x, y;
};
ll distsq(point a, point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long double dist(point a, point b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
ll det(point a, point b, point c){
    return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
long double pant(point a, point b){
    if (a.x==b.x)
        return -inf;
    return (a.y-b.y)/(a.x-b.x);
}
long double trarea(point a, point b, point c){
    ll d=abs(det(a, b, c));
    if (d%2==0)
        return d/2;
    return d/2+0.5;
}
void ecdr(point A, point B, ll &a, ll &b, ll&c){
    a=A.y-B.y;
    b=B.x-A.x;
    c=A.x*(B.y-A.y)-A.y*(B.x-A.x);
}
// segment a-b
bool PctPeSeg(point a, point b, point c){
    return (det(a, b, c)==0 && min(a.x, b.x)<=c.x && max(a.x, b.x)>=c.x
                           && min(a.y, b.y)<=c.y && max(a.y, b.y)>=c.y);
}
bool InterSeg(point a, point b, point c, point d){
    if (PctPeSeg(a, b, c) || PctPeSeg(a, b, d) || PctPeSeg(c, d, a) || PctPeSeg(c, d, b))
        return 1;
    return (det(a, b, c)*det(a, b, d)<0 && det(c, d, a)*det(c, d, b)<0);
}

int n, m;
point v[Nmax], pct;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int crt=0;
    fin>>n>>m;
    for (int i=0; i<n; i++)
        fin>>v[i].x>>v[i].y;
    srand(time(0));
    for (int i=0; i<m; i++){
        fin>>pct.x>>pct.y;
        bool ok=0;
        for (int i=0; i<n; i++){
            int j=(i+1)%n;
            if (PctPeSeg(v[i], v[j], pct))
                ok=1;
        }
        if (ok)
            crt++;
        else{
            bool ok=0;
            int x, y;
            do{
                x=inf+rand()%1000;
                y=inf+rand()%1000;
                for (int i=0; i<n; i++)
                    if (PctPeSeg(pct, {x, y}, v[i]))
                        ok=1;
            }
            while (ok);
            int inter=0;
            for (int i=0; i<n; i++){
                int j=(i+1)%n;
                if (InterSeg(pct, {x, y}, v[i], v[j]))
                    inter++;
            }
            if (inter%2==1)
                crt++;
        }
    }
    fout<<crt;
    return 0;
}