Cod sursa(job #2326883)

Utilizator StefanZamfirStefan Zamfir StefanZamfir Data 24 ianuarie 2019 10:34:43
Problema Poligon Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.69 kb
//#include <iostream>
#include <queue>
#include <stack>
#include <map>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>
#include <algorithm>
#include <bitset>
#include <time.h>
#include <tuple>
#include <fstream>
#include <iomanip>
#include <utility>

#pragma warning "da 100% din tine. :)"
#define nl '\n'
#define sp ' '
#define pb(x) push_back(x)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define SIZE 3000
#define NR 105
#define N 1300000
#define INF 10000
#define ll long long
#define ull unsigned ll
#define F "poligon"

using namespace std;
ifstream cin(F".in");
ofstream cout(F".out");

template<class v, class type>
void print(v Vector, type nr) {
    for_each(all(Vector), [](type x) {
        cout << x << ' ';
    });
}

void nimic() {
    return;
}

float vertx[801], verty[801];
float testx, testy;

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) {
    int i, j, c = 0;
    for (i = 0, j = nvert - 1; i < nvert; j = i++) {
        if (((verty[i] >= testy) != (verty[j] >= testy)) &&
            (testx <= (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]))
            c = !c;
    }
    return c;
}

int sol;

int main() {
    ios_base::sync_with_stdio(false);
//    freopen("caps.in", "r", stdin);
//    freopen("caps.out", "w", stdout);
    clock_t tStart = clock();
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> vertx[i] >> verty[i];
    for (int i = 0; i < m; ++i) {
        cin >> testx >> testy;
        if (pnpoly(n, vertx, verty, testx, testy))
            ++sol;
    }
    cout << sol;

    printf("\nTime taken: %.2fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
}