Pagini recente » Cod sursa (job #367719) | Cod sursa (job #368128) | Cod sursa (job #1745319) | Cod sursa (job #1123126) | Cod sursa (job #1420480)
#include <fstream>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <vector>
#define pe pair<double, double>
#define fi first
#define se second
#define mp make_pair
using namespace std;
ifstream fin("poligon.in");
ofstream fout("poligon.out");
const double PI = 3.14159265359;
const double INF = 10e6;
const int MAX_N = 810;
const double eps = 10e-6;
class cmp {
public:
inline bool operator() (const pe &a, const pe &b) const {
return a.fi + a.se < b.fi + b.se;
}
};
pe R;
inline pe rot(pe x) {
return mp(x.fi * R.fi - x.se * R.se, x.se * R.fi + x.fi * R.se);
}
vector<pe> pol;
vector<double> fas;
vector<pe> A[MAX_N];
inline double getY(double x, pe p1, pe p2) {
return (p1.se * (p2.fi - p1.fi) - (p1.fi - x) * (p2.se - p1.se)) / (p2.fi - p1.fi);
}
inline pe intersect(double x1, double x2, pe p1, pe p2) {
if(p1.fi > p2.fi) {
swap(p1, p2);
}
if(x1 < p1.fi || x2 > p2.fi) {
return mp(-INF, -INF);
}
return mp(getY(x1, p1, p2), getY(x2, p1, p2));
}
void pregen() {
pol.push_back(pol[0]);
for(auto it : pol) {
fas.push_back(it.fi);
}
sort(fas.begin(), fas.end());
fas.erase(unique(fas.begin(), fas.end()), fas.end());
for(int i = 1; i < (int)fas.size(); i++) {
for(int j = 1; j < (int)pol.size(); j++) {
pe x = intersect(fas[i - 1], fas[i], pol[j - 1], pol[j]);
if(x != mp(-INF, -INF)) {
A[i].push_back(x);
}
}
sort(A[i].begin(), A[i].end(), cmp());
}
}
int search(int poz, pe p) {
int st = 0;
int dr = A[poz].size() - 1;
int ans = -1;
while(st <= dr) {
int mij = (st + dr) / 2;
double y = getY(p.fi, mp(fas[poz - 1], A[poz][mij].fi), mp(fas[poz], A[poz][mij].se));
if(p.se > y + eps) {
ans = mij;
dr = mij - 1;
}
else if(p.se < y - eps) {
st = mij + 1;
}
else {
return 1;
}
}
return ans + 1;
}
bool query(pe p) {
if(p.fi < fas[0] || p.se > fas[fas.size() - 1]) {
return false;
}
int ind = lower_bound(fas.begin(), fas.end(), p.fi) - fas.begin();
return search(ind, p) % 2;
}
int main() {
srand(time(NULL));
double ur = (double)(rand() % 10000) / 10000 * PI;
R = mp(cos(ur), sin(ur));
int n, m;
fin >> n >> m;
for(int i = 1; i <= n; i++) {
double x, y;
fin >> x >> y;
pol.push_back(rot(mp(x, y)));
}
pregen();
int ans = 0;
for(int i = 1; i <= m; i++) {
pe x;
fin >> x.fi >> x.se;
x = rot(x);
ans += query(x);
}
fout << ans;
return 0;
}