Cod sursa(job #4420)

Utilizator vlad_DVlad Dumitriu vlad_D Data 3 ianuarie 2007 06:31:33
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#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;
}