Pagini recente » Cod sursa (job #723244) | simulare_oni_11-12 | Cod sursa (job #366325) | Cod sursa (job #2602465) | Cod sursa (job #1488650)
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> Blocks;
vector<vector<int>> LR, RL, Vert;
int n;
bool Taken[100000];
int X[1000], Y[1000];
int det(int i, int x, int y) {
int a = i, b = i-1;
if(X[a] < X[b])
swap(a, b);
return (X[a] - X[b]) * (y - Y[b]) - (Y[a] - Y[b]) * (x - X[b]);
}
#define all(v) v.begin(), v.end()
int bsrc(vector<int> &L, int x, int y) {
int pos = -1, i;
for(i=1; i<=L.size(); i<<=1);
for(i>>=1; i; i>>=1) {
if(i + pos < L.size() && det(L[i+pos], x, y) > 0)
pos += i;
}
return pos;
}
bool onBorder(int x, int y) {
for(int i=1; i<=n; i++)
if(det(i, x, y) == 0) {
if(x >= min(X[i-1], X[i]) && x <= max(X[i-1], X[i]) &&
y >= min(Y[i-1], Y[i]) && y <= max(Y[i-1], Y[i]))
return 1;
}
return 0;
}
bool inPolygon(int x, int y) {
int block = upper_bound(all(Blocks), x) - Blocks.begin() - 1;
int pos1 = bsrc(LR[block], x, y);
block = lower_bound(all(Blocks), x) - Blocks.begin();
int pos2 = bsrc(RL[block], x, y);
int pos3 = -1;
if(Blocks[block] == x)
pos3 = upper_bound(all(Vert[block]), y) - Vert[block].begin() - 1;
return (pos1 + pos2 + pos3) % 2 == 0;
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
int m, x, y;
fin>>n>>m;
Blocks.push_back(0); Taken[0] = 1;
Blocks.push_back(60000); Taken[60000] = 1;
for(int i=1; i<=n; i++) {
fin>>X[i]>>Y[i];
if(!Taken[X[i]])
Blocks.push_back(X[i]), Taken[X[i]] = 1;
}
X[0] = X[n]; Y[0] = Y[n];
sort(all(Blocks));
LR.resize(Blocks.size(), vector<int>());
RL.resize(Blocks.size(), vector<int>());
Vert.resize(Blocks.size(), vector<int>());
for(int i=1; i<=n; i++) {
int block = lower_bound(all(Blocks), X[i-1]) - Blocks.begin();
if(X[i-1] < X[i]) {
while(Blocks[block] != X[i]) {
LR[block].push_back(i);
block++;
}
} else if(X[i-1] > X[i]) {
while(Blocks[block] != X[i]) {
RL[block].push_back(i);
block--;
}
} else {
if(Y[i-1] < Y[i]) Vert[block].push_back(Y[i-1]);
else Vert[block].push_back(Y[i] + 1);
}
}
auto cmp = [&x] (int a, int b) {
int64_t term1 = 1LL * (X[b] - X[b-1]) *
(Y[a-1] * (X[a] - X[a-1]) + (x - X[a-1]) * (Y[a] - Y[a-1]));
int64_t term2 = 1LL * (X[a] - X[a-1]) *
(Y[b-1] * (X[b] - X[b-1]) + (x - X[b-1]) * (Y[b] - Y[b-1]));
return term1 < term2;
};
for(int i=0; i<Blocks.size(); i++) {
x = Blocks[i];
sort(all(LR[i]), cmp);
sort(all(RL[i]), cmp);
sort(all(Vert[i]));
}
// for(int i=0; i<Blocks.size(); i++) {
// cerr<<Blocks[i]<<": LR ";
// for(auto x : LR[i]) {
// cerr<<x<<" ";
// }
// cerr<<"; RL ";
// for(auto x : RL[i]) {
// cerr<<x<<" ";
// }
// cerr<<endl;
// }
int interior = 0;
while(m--) {
fin>>x>>y;
if(onBorder(x, y) || inPolygon(x, y)) {
interior++;
cerr<<x<<" "<<y<<'\n';
}
}
fout<<interior;
return 0;
}