Cod sursa(job #1209899)

Utilizator 2dorTudor Ciurca 2dor Data 18 iulie 2014 20:26:16
Problema Poligon Scor 0
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
//brute-force O(N*M) using areas
ifstream fin("poligon.in");
ofstream fout("poligon.out");

const int MAXN = 805;
const int MAXM = 60005;
int N, M, Sol;

struct punct {
    int x, y;
}polygon[MAXN], crime[MAXM];

long double Area, NewArea;

double Det(punct A, punct B, punct C) {
    double r = A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - A.x * C.y - B.x * A.y;
    return abs(r);
}

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() {
    //first calculate the area of the polygon
    for (int i = 0; i < N; ++i)
        Area += polygon[i].x * polygon[i + 1].y - polygon[i + 1].x * polygon[i].y;
    Area = abs(0.5 * Area);
    //for each point we see if it is inside the polygon
    //by calculating its area and comparing it to the
    //original area of the polygon
    for (int i = 0; i < M; ++i) {
        NewArea = 0.0;
        for (int j = 0; j < N; ++j)
            NewArea += Det(crime[i], polygon[j], polygon[j + 1]);

        NewArea = abs(0.5 * NewArea);

        if (NewArea <= Area)
            ++Sol;
    }
}

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

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