Cod sursa(job #4271)

Utilizator mastermageSchneider Stefan mastermage Data 2 ianuarie 2007 10:51:20
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <stdio.h>

#define maxN 1100
// must revise the limit

int n, xg, yg, x[maxN], y[maxN], res;

void inputFunc(){FILE*fi=fopen("dragon.in", "r");fscanf(fi, "%d %d %d", &n, &xg, &yg);for(int i=0; i<n; i++) fscanf(fi, "%d %d", x+i, y+i);fclose(fi);}
void outputFunc(){FILE*fi=fopen("dragon.out", "w");fprintf(fi, "%d", res);fclose(fi);}

struct point{double x, y;};
struct lequ{int a, b, c;void init(int x1, int y1, int x2, int y2);int solve(int x, int y);point perp(int x, int y);};
void lequ::init(int x1, int y1, int x2, int y2){a=y1-y2; b=x2-x1; c=x1*y2-x2*y1;}
int lequ::solve(int x, int y){int r=a*x + b*y + c;if(!r)return 0;if(r<0)return -1; return 1;}
point lequ::perp(int x, int y){point res;res.y=(a*(a*y-b*x)-b*c)/(double)(a*a+b*b);if(a)res.x=(-c-res.y*b)/a;else res.x=x;return res;}

int next(int c){return c+1<n ? c+1 : 0;}
int max(int a, int b){return a>b?a:b;}
int min(int a, int b){return a<b?a:b;}

int canSleep(int c,int j,point cp)
{
	int max_x=max(x[c],x[j]),min_x=min(x[c],x[j]),max_y=max(y[c],y[j]),min_y=min(y[c],y[j]);
	if((x[c]!=cp.x||y[c]!=cp.y)&&(x[j]!=cp.x||y[j]!=cp.y)&&min_x<=cp.x&&cp.x<=max_x&&min_y<=cp.y&&cp.y<=max_y)return 1;
	return 0;
}

int main()
{
	inputFunc();
	int foundfirst=0,ladded,lst,len,fadded,fst,fen;lequ ledge;

	for(int i=0; i<n; i++){
		int j;lequ cl;
		for(j=next(i); j!=i; j=next(j)){
			cl.init(x[i], y[i], x[j], y[j]);int q, fp=2;
			
			for(q=0; q<n; q++){
				int det= cl.solve(x[q], y[q]);
				if(det)if(fp==2)fp=det;else if(det!=fp)break;
			}
			if(q==n)break;// has been found!
		}
		
		if(j==i)continue;// has NOT been found!
		
		int c=i; if(j<i)i=n;else i=j-1;
		if(foundfirst){
			if( !ledge.solve(x[c], y[c]) && !ledge.solve(x[j], y[j]) ){
				if(ladded)continue;
				c=lst;
			}
		}
		
		if(canSleep(c,j,cl.perp(xg, yg)))
			res++,ladded=1;
		else
			ladded=0;
		
		lst=c,len=j,ledge=cl;if(!foundfirst)fadded=ladded,fst=lst,fen=len,foundfirst=1;
	}
	
	if(!ledge.solve(x[fst],y[fst]) && !ledge.solve(x[fen],y[fen])){
		if(ladded && fadded) res--;
		if(!ladded && !fadded && canSleep(lst,fen,ledge.perp(xg,yg)))res++;
	}
	
	outputFunc();
	return 0;
}