Cod sursa(job #2001133)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 15 iulie 2017 18:51:11
Problema Poligon Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 kb
#include<fstream>
#include<algorithm>
#define x first
#define y second
#define eps 0.00000001
using namespace std;
int n, m, i, j, nr, st, dr, mid, sol, ff, u;
double f[805];
pair<double, double> v[805], w[60005];
struct str{
    double xf, yf, xs, ys;
};
str d[805];
ifstream fin("poligon.in");
ofstream fout("poligon.out");
double det(double X1, double Y1, double X2, double Y2, double X3, double Y3){
    return (X2 - X1) * (Y3 - Y1) - (X3 - X1) * (Y2 - Y1);
}
int cmp(str a, str b){
    return a.yf + a.ys < b.yf + b.ys;
}
double intersect(pair<double, double> p1, pair<double, double> p2, double x2){
    double a, b, c, y2;
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = -a * p1.x - b * p1.y;
    y2 = (-c - a * x2) / b;
    return y2;
}
double modul(double x){
    if(x > 0){
        return x;
    }
    return -x;
}
int comp(double x, double y){
    if(modul(x - y) <= eps){
        return 0;
    }
    if(x > y){
        return 1;
    }
    return -1;
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
        f[i] = v[i].x;
    }
    for(i = 1; i <= m; i++){
        fin>> w[i].x >> w[i].y;
    }
    sort(w + 1, w + m + 1);
    sort(f + 1, f + n + 1);
    ff = 1;
    for(i = 2; i <= n; i++){
        if(comp(f[i], f[ff]) != 0){
            f[++ff] = f[i];
        }
    }
    u = 1;
    while(u <= m && comp(f[1], w[u].x) == 1){
        u++;
    }
    v[n + 1] = v[1];
    for(i = 1; i < ff; i++){
        nr = 0;
        for(j = 1; j <= n; j++){
            if( comp(min(v[j].x, v[j + 1].x), f[i]) != 1 && comp(max(v[j].x, v[j + 1].x), f[i + 1]) != -1 ){
                nr++;
                d[nr].xf = f[i];
                d[nr].xs = f[i + 1];
                d[nr].yf = intersect(v[j], v[j + 1], f[i]);
                d[nr].ys = intersect(v[j], v[j + 1], f[i + 1]);
            }
        }
        sort(d + 1, d + nr + 1, cmp);
        while(u <= m && comp(w[u].x, f[i + 1]) != 1){
            if(det(d[1].xf, d[1].yf, d[1].xs, d[1].ys, w[u].x, w[u].y) < -eps || det(d[nr].xf, d[nr].yf, d[nr].xs, d[nr].ys, w[u].x, w[u].y) > eps){
                u++;
                continue;
            }
            st = 1;
            dr = nr;
            while(st <= dr){
                mid = (st + dr) / 2;
                double det2 = det(d[mid].xf, d[mid].yf, d[mid].xs, d[mid].ys, w[u].x, w[u].y);
                if(det2 < -eps){
                    dr = mid - 1;
                }
                else{
                    st = mid + 1;
                }
            }
            if(modul(det(d[dr].xf, d[dr].yf, d[dr].xs, d[dr].ys, w[u].x, w[u].y) ) <= eps || dr % 2 == 1){
                sol++;
            }
            u++;
        }
    }
    fout<< sol <<"\n";
    return 0;
}