Pagini recente » Cod sursa (job #2576525) | Cod sursa (job #1730892) | Cod sursa (job #1061806) | Cod sursa (job #2649693) | Cod sursa (job #4469)
Cod sursa(job #4469)
#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;
}