Cod sursa(job #1150593)

Utilizator dariusdariusMarian Darius dariusdarius Data 23 martie 2014 12:41:32
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include <cmath>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 800;

vector<int> verticals;
vector< vector<int> > zones;
struct Point {
    int x, y;
} points[MAX_N];
struct Line {
    int a, b, c;
} lines[MAX_N];

inline double get_distance(double x1, double y1, double x2, double y2) {
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
inline bool on_segment(Point &a, Point &b, double x, double y) {
    return fabs(get_distance(1.0 * a.x, 1.0 * a.y, x, y) + get_distance(1.0 * b.x, 1.0 * b.y, x, y) - get_distance(1.0 * a.x, 1.0 * a.y, 1.0 * b.x, 1.0 * b.y)) < 1.e-6;
}

inline double get_y(const int &index, const int &x) {
    return -1.0 * (lines[index].c + lines[index].a * x) / lines[index].b;
}

int x1, x2;
inline int compare(const int &a, const int &b) {
    double y1, y2;
    y1 = -1.0 * (lines[a].c + lines[a].a * (x1 + x2) * 0.5) / lines[a].b;
    y2 = -1.0 * (lines[b].c + lines[b].a * (x1 + x2) * 0.5) / lines[b].b;
    //cout << "Comparing " << a << "(" << y1 << ") with " << b << "(" << y2 << ")\n";
    return y2 - y1 > -1.e-6;
}

int main() {
    ifstream fin("poligon.in");
    ofstream fout("poligon.out");
    int n, queries;
    fin >> n >> queries;
    for(int i = 0; i < n; ++ i) {
        fin >> points[i].x >> points[i].y;
    }
    for(int i = 0; i < n; ++ i) {
        lines[i].a = points[i].y - points[(i + 1) % n].y;
        lines[i].b = points[(i + 1) % n].x - points[i].x;
        lines[i].c = points[i].x * points[(i + 1) % n].y - points[(i + 1) % n].x * points[i].y;
        verticals.push_back(points[i].x);
    }
    sort(verticals.begin(), verticals.end());
    verticals.erase(unique(verticals.begin(), verticals.end()), verticals.end());
    int m = static_cast<int>(verticals.size()) - 1; //number of zones
    zones.assign(m, vector<int>());
    for(int i = 0; i < m; ++ i) {
        for(int j = 0; j < n; ++ j) {
            if(lines[j].b == 0) {
                continue;
            }
            double y1, y2;
            y1 = -1.0 * (lines[j].c + lines[j].a * verticals[i]) / lines[j].b;
            y2 = -1.0 * (lines[j].c - lines[j].a * verticals[i + 1]) / lines[j].b;
            if(on_segment(points[j], points[(j + 1) % n], 1.0 * verticals[i], y1) && on_segment(points[j], points[(j + 1) % n], 1.0*verticals[i + 1], y2)) {
                zones[i].push_back(j);
            }
        }
        x1 = verticals[i]; x2 = verticals[i + 1];
        sort(zones[i].begin(), zones[i].end(), compare);
        //for(int j = 0; j < static_cast<int>(zones[i].size()); ++ j) {
        //    cout << " " << zones[i][j];
        //}
        //cout << "\n";
    }
    int answer = 0;
    for(int i = 0; i < queries; ++ i) {
        int x, y;
        fin >> x >> y;
        if(x < verticals[0] || x > verticals[m]) {
            continue;
        }
        int zone = -1;
        for(int pas = 512; pas; pas >>= 1) {
            if(zone + pas < m && x >= verticals[zone + pas]) {
                zone += pas;
            }
        }
        int count = -1;
        for(int pas = 512; pas; pas >>= 1) {
            if(count + pas < static_cast<int>(zones[zone].size()) && y - get_y(zones[zone][count + pas], x) > -1.e-6) {
                count += pas;
            }
        }
        if(fabs(y - get_y(zones[zone][count], x)) < 1.e-6 || (count % 2 == 0)) {
            ++ answer;
        }
    }
    fout << answer << "\n";
    return 0;
}