Cod sursa(job #1056)

Utilizator Spike7d5Spike7d5 Spike7d5 Data 12 decembrie 2006 15:33:09
Problema Poligon Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define MPOLI 805
#define MPCT  60005

int intersectie (int x1, int y1, int x3, int y3, int x4, int y4) {
int x2, y2, num;
float ua, ub;

x2=-10; y2=y1+10;
num=(y4-y3)*(x2-x1)-(x4-x3)*(y2-y1);
ua=(x4-x3)*(y1-y3)-(y4-y3)*(x1-x3);
ub=(x2-x1)*(y1-y3)-(y2-y1)*(x1-x3);

if (num==0) return 0;
ua/=num;
ub/=num;

if ((-0.0001<=ua && ua<=0.0001) || (0.9999<=ua && ua<=1.0001)) return 1000;

if (0<=ub && ub<=1) return 1;
return 0;
}

int main () {
freopen ("poligon.in", "rt", stdin);
freopen ("poligon.out", "wt", stdout);

int polix[MPOLI], poliy[MPOLI], pctx[MPCT], pcty[MPCT], i, j, n, m, sol, tmp;
scanf ("%d%d", &n, &m);
for (i=0;i<n;i++) scanf ("%d%d", &polix[i], &poliy[i]);
polix[n]=polix[0]; poliy[n]=poliy[0];
for (i=0;i<m;i++) scanf ("%d%d", &pctx[i], &pcty[i]);

sol=0;
for (i=0;i<m;i++) {
  tmp=0;
  for (j=0;j<n;j++)
    tmp+=intersectie (pctx[j], pcty[j], polix[i], poliy[i], polix[i+1], poliy[i+1]);
  if (tmp>=1000)
    sol++;
  else
    sol+=tmp%2; }

printf ("%d\n", sol);

return 0; }