Cod sursa(job #4544)

Utilizator MARCELMIHALCEA MARICEL MARCEL Data 5 ianuarie 2007 13:21:29
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define Nmax 1001

struct punct{
long x,y;} d[Nmax], g;
long viz[Nmax],s[Nmax],n,top=2,sol=0;


int sort_function( const void *a, const void *b)
{

punct p1,p2;

p1=* (punct *)a;
p2=* (punct *)b;

if( p1.y<p2.y ) return -1;
if( p1.y>p2.y ) return 1;

return ( p1.x-p2.x );

}


int sens(punct p,punct q,punct r)
 {
  if( ( (q.x-p.x)*(r.y-p.y) - (r.x-p.x)*(q.y-p.y)  ) > 0 )
		   return 0;
  return 1;
 }

  void hill()
  {
  long i;

   qsort((void *)(d+1), n, sizeof(d[0]), sort_function);

d[0]=d[1];s[1]=1;s[2]=2;viz[1]=viz[2]=1;

 for(i=3;i<=n;i++)
	if( !viz[i] )
	  if ( sens(d[s[top-1]],d[s[top]],d[i]) )
		{
		viz[s[top--]]=0;
		i--;
		 }
	else {
	  viz[i]=1;
	  s[++top]=i;
	   }

	viz[1]=0;
 for(i=n-1;i>0;i--)
	if( ! viz[i] )
	  if ( sens(d[s[top-1]],d[s[top]],d[i]) )
		{
		viz[s[top--]]=0;
		i++;
		 }
	else
	 {
	 viz[i]=1;
	 s[++top]=i;
	  }

   }


 int between(  punct a, punct b )
  {

  float d1,d2,d3,u1,u2;

  d1 = sqrt ( (float) ( (a.x-g.x)*(a.x-g.x) + (a.y-g.y)*(a.y-g.y) ) ) ;
  d2 = sqrt ( (float) ( (b.x-g.x)*(b.x-g.x) + (b.y-g.y)*(b.y-g.y) ) ) ;
  d3 = sqrt ( (float) ( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) ) ) ;

  u1 = (- d1*d1+d2*d2+d3*d3 ) / (d2*d3*2) ;
  u2 = (- d2*d2+d1*d1+d3*d3 ) / (d1*d3*2) ;

  u1 = long(u1*100000) ;
  u1 = u1 / 100000;
  u2 = long(u2*100000) ;
  u2 = u2 / 100000;

   if ( u1 > 0 && u2 > 0 )	return 1;

   return 0;
  }


void solve()
 {
 long i;

 for ( i =1 ; i < top ;i ++ )
	  if( between(d[s[i]],d[s[i+1]]) ) sol ++ ;

 }


void read_data()
{
long i;

FILE *f=fopen("dragon.in","r");

fscanf(f,"%ld%ld%ld",&n,&g.x,&g.y);

for( i=1 ; i<=n; i ++ )
 fscanf( f, "%ld%ld", &d[i].x, &d[i].y );

 fclose(f);

 return ;
  }


void print_data()
{
FILE *g=fopen("dragon.out","w");

fprintf(g,"%ld\n",sol);

fclose(g);

}


int main()
{

read_data();

hill();

solve();

print_data();

return 0;

}