Cod sursa(job #1217715)

Utilizator SRaduRadu Szasz SRadu Data 8 august 2014 00:10:43
Problema Poligon Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.73 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;

const int MAX = 810;
const double ANGLE = 0.01;
const double EPS = 1e-6;

typedef pair<double, double> POINT;
#define x first
#define y second

int N, M, NX, Ans;

bool onEdge;

double Left, Right;
double X[MAX], A[MAX], B[MAX], C[MAX], UseA[MAX], UseC[MAX];

POINT V[MAX];

vector<int> Strip[MAX];

POINT Rotate(const int &X, const int &Y, const double &Angle) {
    POINT Ans;
    Ans.x = cos(Angle) * X - sin(Angle) * Y;
    Ans.y = sin(Angle) * X + cos(Angle) * Y;
    return Ans;
}

bool EQUAL(const double &A, const double &B) {
    if(fabs(A - B) < EPS)
        return true;
    return false;
}

bool cmp(const int &i, const int &j) {
    double Mid = (Left + Right) / 2.0;
    return UseA[i] * Mid + UseC[i] < UseA[j] * Mid + UseC[j];
}

bool isBelow(const int &ind, const POINT &P) {
    if(EQUAL(A[ind] * P.x + B[ind] * P.y + C[ind], 0.0))
        onEdge = true;
    if(B[ind] >= 0)
        return A[ind] * P.x + B[ind] * P.y + C[ind] >= 0;
    return A[ind] * P.x + B[ind] * P.y + C[ind] <= 0;
}

int main() {
//citire poligon
    ifstream in("poligon.in");
    in >> N >> M;
    for(int i = 1, A, B; i <= N; i++) {
        in >> A >> B;
        V[i] = Rotate(A, B, ANGLE);
        X[i] = V[i].x;
    } 
    V[N + 1] = V[1];
    
//preprocess
    sort(X + 1, X + N + 1);
    NX = 1;
    for(int i = 2; i <= N; i++) {
        if(!EQUAL(X[i], X[NX]))
            X[++NX] = X[i];
    }

    for(int i = 1; i <= N; i++) {
        A[i] = V[i + 1].y - V[i].y;
        B[i] = V[i].x - V[i + 1].x;
        C[i] = V[i + 1].x * V[i].y - V[i].x * V[i + 1].y;
        UseA[i] = -A[i] / B[i];
        UseC[i] = -C[i] / B[i];
    }

    for(int i = 1; i <= NX; i++) {
        Left = X[i], Right = X[i + 1];
        
        for(int j = 1; j <= N; j++) 
            if(min(V[j].x, V[j + 1].x) <= Left && Left < max(V[j].x, V[j + 1].x)) 
                Strip[i].push_back(j);
        
        sort(Strip[i].begin(), Strip[i].end(), cmp);
    }

//solve
    for(int t = 1, A, B; t <= M; t++) {
        in >> A >> B;
        POINT Q = Rotate(A, B, ANGLE);

        if(Q.x < X[1] && X[NX] < Q.x)
            continue;

        onEdge = false;

        int Region = 0;
        for(int Step = 1024; Step; Step >>= 1) 
            if(Step + Region < NX && X[Step + Region] < Q.x)
                Region += Step;
        
        int Below = 0;
        for(int Step = 1024; Step; Step >>= 1)
            if(Step + Below <= Strip[Region].size() && isBelow(Strip[Region][Step + Below - 1], Q))
                Below += Step;

        if(Below & 1 || onEdge) {
            Ans++;
        }

    } in.close();

//afisare
    ofstream out("poligon.out");
    out << Ans << "\n";
    out.close();
}