Cod sursa(job #897928)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 27 februarie 2013 23:02:17
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
//X[i] - coordonatele X initiale, pe baza carora formez benzile
//Y[i] - coordonatele X normalizate. Doua elemente consecutive din Y delimiteaza o banda
//V[i] - setul initial de puncte
//A[i], B[i], C[i] - coeficientii ecuatiei dreptei
//Band[i] - indicii dreptelor din banda i
//Banda i este cea delimitata de Y[i] si Y[i + 1]
//Dreapta i este dreapta determinata de punctele V[i] si V[i + 1]
//mid - mijlocul benzii actuale
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>

#define PII pair<int, int>
#define x first
#define y second
#define MAX 805

using namespace std;

int N, M, ans;
int X[MAX], Y[MAX], A[MAX], B[MAX], C[MAX];
double mid;
PII V[MAX], P;
vector<int> Band[MAX];

//sortez dreptele dintr-o banda dupa mijlocul lor
bool cmp(int i, int j) {
   double a = (1.0 * (-C[i]) - (mid * A[i])), b = (1.0 * (-C[j]) - (mid * A[j]));
   return a / (1.0 * B[i]) < b / (1.0 * B[j]);
}

bool ok(int D, PII P) {
    return A[D] * P.x + B[D] * P.y + C[D] <= 0;
}

int main() {
    //citesc
    ifstream in("poligon.in");
    in>>N>>M;
    for(int i = 1; i <= N; i++) {
        in>>V[i].x>>V[i].y;
    } V[N + 1] = V[1];
    //normalizez
    for(int i = 1; i <= N; i++) {
        X[i] = V[i].x;
    } sort(X + 1, X + N + 1);
    Y[++Y[0]] = X[1];
    for(int i = 2; i <= N; i++)
        if(X[i] != X[i - 1]) {
            Y[++Y[0]] = X[i];
        }
    //calculez ecuatia dreptei pt fiecare din cele N drepte
    for(int i = 1; i <= N; i++) {
        A[i] = V[i].y - V[i + 1].y;
        B[i] = V[i + 1].x - V[i].x;
        C[i] = V[i].x * V[i + 1].y - V[i].y * V[i + 1].x;
    }
    //aflu liniile dintr-o banda
    for(int i = 1; i < Y[0]; i++) {

        for(int j = 1; j <= N; j++) {
            if(min(V[j].x, V[j + 1].x) <= Y[i] && Y[i] < max(V[j].x, V[j + 1].x))
                Band[i].push_back(j);
        }
        mid = (1.0 * Y[i] + Y[i + 1]) / 2.0;
        sort(Band[i].begin(), Band[i].end(), cmp);
    }
    //rezolv query-urile
    while(M--) {
        in>>P.x>>P.y;
        if(P.x < Y[1] || P.x > Y[Y[0]]) continue;
        int band = 0;
        for(int step = 1024; step; step >>= 1) if(band + step <= Y[0] && Y[band + step] < P.x) band += step;
        int line = -1;
        for(int step = 1024; step; step >>= 1) {
            if(line + step < Band[band].size() && ok(Band[band][line + step], P)) line += step;
        }
        ans += (line + 2) % 2;
        //if(line % 2) cerr<<P.x<<" "<<P.y<<"\n";
    }
    ofstream out("poligon.out"); out<<ans<<"\n"; out.close();
    return 0;
}