Pagini recente » Rating Teo Serbanescu (teo.serbanescu) | Cod sursa (job #2742357) | Cod sursa (job #837964) | Cod sursa (job #3290366) | Cod sursa (job #1718148)
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <fstream>
using namespace std;
const int kMaxN = 805;
#define pb push_back
#define mp make_pair
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;
int n, m;
double x[kMaxN], y[kMaxN], from[kMaxN], to[kMaxN], fromX[kMaxN], dif[kMaxN];
int ox[kMaxN], oy[kMaxN], a[kMaxN], b[kMaxN];
LL c[kMaxN];
const double ANG = 0.12319212341941234901;
const double CANG = cos(ANG);
const double SANG = sin(ANG);
const double EPS = 1e-9;
int main() {
freopen("poligon.in", "r", stdin);
freopen("poligon.out", "w", stdout);
scanf("%d%d", &n, &m);
REP(i, n) {
int tx, ty;
scanf("%d%d", &tx, &ty);
ox[i] = tx;
oy[i] = ty;
x[i] = CANG * tx - SANG * ty;
y[i] = SANG * tx + CANG * ty;
}
x[n] = x[0];
y[n] = y[0];
ox[n] = ox[0];
oy[n] = oy[0];
REP(i, n) {
a[i] = oy[i] - oy[i + 1];
b[i] = ox[i + 1] - ox[i];
c[i] = -((LL)a[i] * ox[i] + (LL)b[i] * oy[i]);
}
REP(i, n) {
if (y[i] < y[i + 1]) {
from[i] = y[i];
to[i] = y[i + 1];
dif[i] = (x[i + 1] - x[i]) / (to[i] - from[i]);
fromX[i] = x[i] - dif[i] * from[i];
} else {
from[i] = y[i + 1];
to[i] = y[i];
dif[i] = (x[i] - x[i + 1]) / (to[i] - from[i]);
fromX[i] = x[i + 1] - dif[i] * from[i];
}
}
int ans = 0;
REP(q, m) {
int tx, ty;
scanf("%d%d", &tx, &ty);
bool boundary = false;
REP(i, n) {
if ((LL)a[i] * tx + (LL)b[i] * ty + c[i] == 0) {
if (tx >= min(ox[i], ox[i + 1]) && tx <= max(ox[i], ox[i + 1])) {
if (ty >= min(oy[i], oy[i + 1]) && ty <= max(oy[i], oy[i + 1])) {
boundary = true;
break;
}
}
}
}
if (boundary) {
++ans;
continue;
}
continue;
double xx = CANG * tx - SANG * ty;
double yy = SANG * tx + CANG * ty;
int res = 0;
REP(i, n) {
if (yy > from[i] - EPS && yy < to[i] + EPS) {
if (fromX[i] + dif[i] * yy > xx - EPS) {
res ^= 1;
}
}
}
// ans += res;
}
printf("%d\n", ans);
return 0;
}