Cod sursa(job #1211762)

Utilizator 2dorTudor Ciurca 2dor Data 23 iulie 2014 11:53:22
Problema Poligon Scor 20
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.72 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
using namespace std;
//O(N*M) using a ray
ifstream fin("poligon.in");
ofstream fout("poligon.out");

const int MAXN = 805;
const int MAXM = 60005;
const int INF = 0x3f3f3f3f;
int N, M, Sol, CutEdges;

struct point {
    double x, y;
}polygon[MAXN], crime[MAXM];

inline double slope(point A, point B) {
    if (A.x - B.x == 0)
        return INF;
    return (A.y - B.y) / (A.x - B.x);
}

void Read() {
    fin >> N >> M;
    for (int i = 0; i < N; ++i)
        fin >> polygon[i].x >> polygon[i].y;
    polygon[N] = polygon[0];
    for (int i = 0; i < M; ++i)
        fin >> crime[i].x >> crime[i].y;
}

void Solve() {
    for (int i = 0; i < M; ++i) {
        //take each point and draw a horizontal ray to the right
        point P = crime[i];
        //and see how many edges it cuts
        double m;
        CutEdges = 0;
        for (int j = 0; j < N; ++j) {
            //first, check if the ray passes through this edge, either on the left or on the right
            if ( ((polygon[j].y  < P.y) and (P.y < polygon[j + 1].y))
              || ((polygon[j + 1].y  < P.y) and (P.y < polygon[j].y)) ) {
                //now check if the intersection point
                //is on the right semi-plane of the x-coordinate
                m = slope(polygon[j], polygon[j + 1]);
                double x = (P.y - polygon[j].y) / m + polygon[j].x;
                if (P.x < x)
                    ++CutEdges;
            }
        }
        Sol += CutEdges % 2;
    }
}

void Write() {
    fout << Sol << '\n';
}

int main() {
    Read();
    Solve();
    Write();
    fin.close();
    fout.close();
    return 0;
}