Cod sursa(job #4469)

Utilizator MARCELMIHALCEA MARICEL MARCEL Data 3 ianuarie 2007 17:17:38
Problema Jocul Flip Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb

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

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



	  // hill
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()
  {

   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(int 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;
	  }

   }

   // end hill


 int between(  punct a, punct b ) // daca pr lui g pe ab se afla pe (ab)
  {

  float d1,d2,d3,u1,u2;

  d1 = sqrt ( (a.x-g.x)*(a.x-g.x) + (a.y-g.y)*(a.y-g.y) ) ;
  d2 = sqrt ( (b.x-g.x)*(b.x-g.x) + (b.y-g.y)*(b.y-g.y) ) ;
  d3 = sqrt ( (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) ;

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


   return 0;
  }


void solve()
 {

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

 }


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

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

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

 fclose(f);

 return ;
  }


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

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

fclose(g);

}


int main()
{

read_data();

hill();

solve();

print_data();

return 0;

}