Pagini recente » Cod sursa (job #1668031) | Cod sursa (job #3152134) | Cod sursa (job #421574) | Cod sursa (job #2389419) | Cod sursa (job #4420)
Cod sursa(job #4420)
#include <stdio.h>
struct point {double x, y;} v[1200], v2[1200];
int N;
int N2;
int i, j, p;
int ret = 0;
int used[1200];
int main() {
freopen("dragon.in", "r", stdin);
freopen("dragon.out", "w", stdout);
scanf("%d", &N);
point D;
scanf("%lf %lf", &D.x, &D.y);
for (i=1; i<=N; i++) {
int a, b;
scanf("%d %d", &a, &b);
v[i].x = a; v[i].y = b;
}
//cauta cel mai din stanga
j = 1;
for (i = 2; i<=N; i++) {
if (v[i].x < v[j].x) j = i;
if (v[i]. x == v[j].x && v[i].y > v[j].y) j = i;
}
int start = j;
p = j;
N2++; v2[N2] = v[p];
do {
int n = -1;
double dist = 999999;
for (i=1; i<=N; i++) {
if (i == p) continue;
if (used[i]) continue;
if (n == -1) n = i;
double cross = (v[i].x - v[p].x)*(v[n].y-v[p].y) - (v[i].y-v[p].y)*(v[n].x - v[p].x);
double d = (v[i].x-v[p].x)*(v[i].x - v[p].x) + (v[i].y-v[p].y)*(v[i].y-v[p].y);
if (cross < 0) {n = i; dist = d;}
else if (cross == 0) {
if (d > dist) {dist = d; n = i ;}
}
}
p = n;
N2++; v2[N2] = v[p];
used[p] = 1;
} while (start!=p);
for (i=1; i<=N2; i++) v[i] = v2[i];
for (i=1; i<N2; i++) {
//i ,i+1
double A1 = v[i+1].y - v[i].y, B1= v[i].x - v[i+1].x;
double A2 = - (v[i].x - v[i+1].x);
double B2 = v[i+1].y - v[i].y;
double C2 = A2*D.x + B2*D.y;
double C1 = A1*v[i].x + B1*v[i].y;
double det = A1*B2 - A2*B1;
point M; M.x = (B2*C1 - B1*C2)/det;
M.y = (A1*C2 - A2*C1)/det;
double a = v[i].x, b = v[i+1].x;
if (v[i+1].x < v[i].x) {a=v[i+1].x; b=v[i].x;}
int ok= 0;
if (M.x >= a && M.x <= b) ok++;
a = v[i].y, b = v[i+1].y;
if (v[i+1].y < v[i].y) {a=v[i+1].y; b=v[i].y;}
if (M.y >= a && M.y <= b) ok++;
if ((M.x == v[i].x && M.y == v[i].y) || (M.x == v[i+1].x && M.y == v[i+1].y)) ok--;
if (ok ==2 ) { ret++;}
}
printf("%d\n", ret);
return 0;
}