Pagini recente » Diferente pentru teorema-chineza-a-resturilor intre reviziile 48 si 89 | Monitorul de evaluare | Cod sursa (job #962024) | Monitorul de evaluare | Cod sursa (job #1746979)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int kMaxN = 805;
const double kEps = 1e-6;
int Compare(double a, double b) {
if(a - b > kEps) return 1;
if(b - a > kEps) return -1;
return 0;
}
struct Point {
double x;
double y;
Point() {}
Point(double _x, double _y) { x = _x; y = _y; }
};
struct Segment {
Point a;
Point b;
Segment() {}
Segment(Point _a, Point _b) { a = _a; b = _b; }
Point Middle() const { return Point((a.x + b.x) / 2, (a.y + b.y) / 2); }
inline bool operator <(Segment const& other) const { return Compare(Middle().y, other.Middle().y) == -1; }
};
int N, Q;
Point P[kMaxN];
vector<int> xCoords;
vector<vector<Segment>> Strips;
int CrossProduct(Point a, Point b, Point c) {
double termFi = (b.x - a.x) * (c.y - a.y);
double termSe = (b.y - a.y) * (c.x - a.x);
return (Compare(termFi, termSe) == -1 ? -1 : Compare(termFi, termSe) == 0 ? 0 : 1);
}
int main() {
ifstream fin("poligon.in");
ofstream fout("poligon.out");
fin >> N >> Q;
for(int i = 1; i <= N; i++) {
fin >> P[i].x >> P[i].y;
xCoords.push_back(P[i].x);
}
sort(xCoords.begin(), xCoords.end());
xCoords.erase(unique(xCoords.begin(), xCoords.end()), xCoords.end());
for(int i = 0; i < xCoords.size() - 1; i++) {
Strips.push_back(vector<Segment>());
for(int j = 1; j <= N; j++) {
Point pHere = P[j];
Point pThere = P[(j == N ? 1 : j + 1)];
if(pHere.x > pThere.x) swap(pHere, pThere);
if(pHere.x < pThere.x && pHere.x <= xCoords[i] && xCoords[i + 1] <= pThere.x) {
double a = pHere.y - pThere.y;
double b = pThere.x - pHere.x;
double c = -(a * pHere.x + b * pHere.y);
double yHere = -(a * pHere.x + c) / b;
double yThere = -(a * pHere.x + c) / b;
Strips.back().push_back(Segment(Point(xCoords[i], yHere), Point(xCoords[i + 1], yThere)));
}
}
sort(Strips.back().begin(), Strips.back().end());
}
int solCnt = 0;
while(Q--) {
int x, y;
fin >> x >> y;
if(x < xCoords.front() || xCoords.back() < x) continue;
int sId = lower_bound(xCoords.begin(), xCoords.end(), x) - xCoords.begin() - 1;
if(sId == -1) sId++;
int lef = 0, rig = Strips[sId].size() - 1;
bool colinear = 0;
while(lef <= rig) {
int med = (lef + rig) >> 1;
int sgn = CrossProduct(Strips[sId][med].a, Strips[sId][med].b, Point(x, y));
if(!sgn) colinear = 1, lef = rig + 1;
else if(sgn < 0) rig = med - 1;
else if(sgn > 0) lef = med + 1;
}
if((lef & 1) || colinear) solCnt++;
}
fout << solCnt << "\n";
return 0;
}