Pagini recente » Cod sursa (job #923896) | Cod sursa (job #1196536) | Cod sursa (job #1038427) | Cod sursa (job #2096381) | Cod sursa (job #1044328)
#include <fstream>
#include <algorithm>
#include <set>
#include <vector>
#include <utility>
#include <iostream>
#define fun(x) ((int)(m * (x) + b))
using namespace std;
struct point{int x,y;};
const int MAX_N = 801;
const int MAX_M = 60001;
int n,m;
point poli[MAX_N];
point qry[MAX_M];
vector<int> zone;
vector< pair<point, point> > strip[MAX_N];
vector<int> no_dups(){
set<int> T;
for(int i = 1 ; i <= n ; ++i)
T.insert(poli[i].x);
return vector<int>(T.begin(), T.end());
}
void check(point const &A, point const &B, int const ind){
if(B.x < A.x)
return check(B, A, ind);
if(A.x <= zone[ind] && zone[ind + 1] <= B.x){
int const delX = B.x - A.x,
delY = B.y - A.y;
if(delX == 0)
return;
strip[ind].push_back(make_pair(A, B));
}
}
int ccw(point const &A, point const &B, point const &C){
int const x1 = B.x - A.x,
x2 = C.x - A.x;
int const y1 = B.y - A.y,
y2 = C.y - A.y;
return x1 * y2 - x2 * y1;
}
int above(point const &P, pair<point, point> const &seg){
int const cross = ccw(seg.first, seg.second, P);
if(cross == 0)
return -1;
else return cross > 0;
}
bool comp(const pair<point, point> &A, const pair<point, point> &B){
return (bool)above(A.first, B) || (bool)above(A.second, B);
}
void preprocess(){
zone = no_dups();
for(size_t z = 0 ; z < zone.size() - 1 ; ++z){
for(int i = 0 ; i < n ; ++i)
check(poli[i], poli[(i+1) % n], z);
sort(strip[z].begin(), strip[z].end(), comp);
reverse(strip[z].begin(), strip[z].end());
}
}
bool cmp(const point &A, const point &B){
return A.x < B.x;}
void read(){
ifstream in("poligon.in");
in >> n >> m;
for(int i = 0 ; i < n ; ++i)
in >> poli[i].x >> poli[i].y;
for(int i = 1 ; i <= m ; ++i)
in >> qry[i].x >> qry[i].y;
}
bool bsearch(point const &P, int const idx){
int i;
size_t step;
for(step = 1 ; step <= strip[idx].size() ; step <<= 1);
bool on_side = 0;
for(i = -1 ; step ; step >>= 1){
if(i + step < strip[idx].size()){
int const cnd = above(P, strip[idx][i + step]);
if(cnd == -1)
on_side = 1;
else if(cnd)
i += step;
}
}
return ((i + 1) % 2 == 1) || on_side;
}
int main(){
read();
preprocess();
sort(qry + 1, qry + m + 1, cmp);
int tot = 0;
size_t now = 0;
for(int i = 1 ; i <= m ; ++i){
while(qry[i].x < zone[now] && i <= m)
++i;
while(zone[now + 1] < qry[i].x && now < zone.size() - 1)
++now;
if(i <= m && now < zone.size() - 1)
tot += bsearch(qry[i], now);
}
ofstream out("poligon.out");
out << tot << "\n";
}