Pagini recente » Cod sursa (job #723179) | Cod sursa (job #3130999) | Cod sursa (job #1011962) | Cod sursa (job #2278471) | Cod sursa (job #1217715)
#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();
}