Cod sursa(job #1100351)

Utilizator dariusdariusMarian Darius dariusdarius Data 6 februarie 2014 20:22:47
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.79 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
const int MAX_N = 805;
const double eps = 1.e-7;

struct PointXY {
    double x, y;
} a[MAX_N];
double paralels_to_oy[MAX_N];
double start_x, end_x;
bool compare(const pair<double, double> &a, const pair<double, double> &b) {
    double a1 = a.first - a.second;
    double b1 = end_x - start_x;
    double c1 = a.second * start_x - a.first * end_x;
    
    double a2 = b.first - b.second;
    double b2 = end_x - start_x;
    double c2 = b.second * start_x - b.first * end_x;

    double middle1 = (- c1 - a1 * (start_x + end_x) * 0.5) / b1;
    double middle2 = (- c2 - a2 * (start_x + end_x) * 0.5) / b2;

    return middle2 - middle1 >= eps;
}
struct Section {
    double start_x, end_x;
    vector< pair<double, double> > segments;
} sections[MAX_N];

pair<double, double> get_points(PointXY &A, PointXY &B, double x1, double x2) {
    double a = A.y - B.y;
    double b = B.x - A.x;
    double c = A.x * B.y - A.y * B.x;
    //a * x1 + b * y1 + c = 0 => y1 = (- c - a * x1) / b
    return make_pair((- c - a * x1) / b, (- c - a * x2) / b);
}
vector< pair<int, pair<int, int> > > verticals;
inline int on_verticals(PointXY &p) {
    if(verticals.empty()) {
        return 0;
    }
    int left = 0, right = static_cast<int>(verticals.size()) - 1, middle;
    while(left <= right) {
        middle = (left + right) / 2;
        if(verticals[middle].first == p.x) {
            break;
        } else if(verticals[middle].first < p.x) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    if(verticals[middle].first != p.x) {
        return 0;
    }
    return min(verticals[middle].second.first, verticals[middle].second.second) <= p.y && 
                p.y <= max(verticals[middle].second.first, verticals[middle].second.second);
}
inline bool above(PointXY &p, Section &section, int index) {
    double a = section.segments[index].first - section.segments[index].second;
    double b = section.end_x - section.start_x;
    double c = section.start_x * section.segments[index].second - section.end_x * section.segments[index].first;
    double y = (- c - a * p.x) / b;
    //cout << y << " " << p.y << "\n";
    return y - p.y > -eps;
}
int main() {
    ifstream fin("poligon.in");
    ofstream fout("poligon.out");
    int n, m, k = 0;
    fin >> n >> m;
    for(int i = 0; i < n; ++ i) {
        fin >> a[i].x >> a[i].y;
        paralels_to_oy[i] = a[i].x;
    }
    sort(paralels_to_oy, paralels_to_oy + n);
    for(int i = 1; i < n; ++ i) {
        if(paralels_to_oy[i] != paralels_to_oy[i - 1]) {
            ++ k;
            sections[k].start_x = paralels_to_oy[i - 1];
            sections[k].end_x = paralels_to_oy[i];
            for(int j = 0; j < n; ++ j) {
                if(a[j].x <= sections[k].start_x && sections[k].end_x <= a[(j + 1) % n].x) {
                    sections[k].segments.push_back(get_points(a[j], a[(j + 1) % n], sections[k].start_x, sections[k].end_x));
                }
                if(a[j].x >= sections[k].end_x && sections[k].start_x >= a[(j + 1) % n].x) {
                    sections[k].segments.push_back(get_points(a[j], a[(j + 1) % n], sections[k].start_x, sections[k].end_x));
                }
            }
        }
        start_x = sections[i].start_x;
        end_x = sections[i].end_x;
        sort(sections[i].segments.begin(), sections[i].segments.end(), compare);
    }
    for(int i = 0; i < n; ++ i) {
        if(a[i].x == a[(i + 1) % n].x) {
            verticals.push_back(make_pair(a[i].x, make_pair(a[i].y, a[(i + 1) % n].y)));
        }
    }
    sort(verticals.begin(), verticals.end());
    int count = 0;
    for(int i = 1; i <= m; ++ i) {
        PointXY p;
        fin >> p.x >> p.y;
        if(p.x < sections[1].start_x || p.x > sections[k].end_x) {
            fout << "-1\n";
            continue;
        }
        if(on_verticals(p)) {
            ++ count;
            continue;
        }
        int section = 0;
        for(int pas = 512; pas; pas >>= 1) {
            if(section + pas <= k && p.x >= sections[section + pas].start_x) {
                section += pas;
            }
        }
        //cout << "Section #" << section << "\n";
        //for(int i = 0; i < static_cast<int>(sections[section].segments.size()); ++ i) {
        //    cout << sections[section].segments[i].first << " " << sections[section].segments[i].second << "\n";
        //}
        int how_many = -1;
        for(int pas = 512; pas; pas >>= 1) {
            if(how_many + pas < static_cast<int>(sections[section].segments.size()) && !above(p, sections[section], how_many + pas)) {
                how_many += pas;
            }
        }
        //cout << how_many << "\n";
        if(how_many % 2 == 0) {
            ++ count;
        }
    }
    fout << count << "\n";
    return 0;
}