Pagini recente » Cod sursa (job #2743931) | Cod sursa (job #2317568) | Cod sursa (job #963820) | Cod sursa (job #1600040) | Cod sursa (job #1388157)
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
typedef int var;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
struct Punct {
var x, y;
Punct(var a, var b) {
x = a;
y = b;
}
};
typedef pair<Punct, Punct> ppp;
#define mp make_pair
vector<Punct> Poligon;
vector<Punct> Puncte;
vector<ppp> Sector[700];
vector<var> PuncteX;
bool check(Punct P, var ind) {
vector<ppp> &S = Sector[ind];
//var n = S.size();
bool isinside = 0;
for(auto p : S) {
//Tragem dreapta verticala
Punct A = p.first,
B = p.second;
//if(A.x > B.x) swap(A, B);
if(P.x <= A.x || P.x > B.x)
continue;
//Semnul determinantului
//| i j k|
//|x2-x1 y2-y1 0|
//|x-x1 y-y1 0|
if((P.y-A.y)*(B.x-A.x) <= (P.x-A.x)*(B.y-A.y)) {
isinside ^= 1;
}
}
return isinside;
}
int main() {
var n, m;
var x, y;
fin >> n >> m;
for(var i=1; i<=n; i++) {
fin>>x>>y;
Poligon.push_back(Punct(x, y));
PuncteX.push_back(x);
}
Poligon.push_back(Poligon[0]);
const var INF = 100000;
PuncteX.push_back(-INF);
PuncteX.push_back(INF);
sort(PuncteX.begin(), PuncteX.end());
for(var p=2; p<PuncteX.size(); p++) {
for(var i=1; i<=n; i++) {
Punct A = Poligon[i],
B = Poligon[i-1];
if(A.x > B.x) swap(A, B);
if(A.x <= PuncteX[p-1] && B.x >= PuncteX[p]) {
Sector[p-1].push_back(mp(A, B));
}
}
}
/*
for(var i=0; i<PuncteX.size()-1; i++) {
fout<<"Sectorul : "<<i<<" dat de "<<PuncteX[i]<<" "<<PuncteX[i+1]<<" :\n";
for(auto p : Sector[i]) {
fout<<"|"<<p.first.x<<" "<<p.first.y<<", "<<p.second.x<<" "<<p.second.y<<"| ";
}
fout<<endl;
}
*/
var sum = 0;
var MAX;
var s = PuncteX.size() - 1;
for(MAX=1; MAX<=PuncteX.size(); MAX<<=1);
MAX >>= 1;
while(m--) {
fin >> x >> y;
var i, ind=0;
for(i=MAX; i; i>>=1) {
if(i+ind <= s && x >= PuncteX[i+ind])
ind+=i;
}
//ind++;
Punct P(x, y);
//fout<<"Sectorul lui "<<x<<" "<<y<<" este "<<ind<<'\n';
sum += check(P, ind);
}
fout << sum;
return 0;
}