Pagini recente » Cod sursa (job #1334670) | Cod sursa (job #2152330) | Cod sursa (job #146330) | Cod sursa (job #2713480) | Cod sursa (job #897928)
Cod sursa(job #897928)
//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;
}