Cod sursa(job #2865)

Utilizator gigi_becaliGigi Becali gigi_becali Data 19 decembrie 2006 17:34:15
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <math.h>
#define maxn 1024

using namespace std;
struct point { int x, y;};
point x[maxn], S[maxn], P0;
int i, j, n, t;
point pi;

double dist(point a, point b)
{
  return sqrt( (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y) );
}

void citire()
{
  freopen("dragon.in", "r", stdin);
  scanf("%d %d %d\n", &n, &pi.x, &pi.y);

  for(int i=0;i<n;i++)scanf("%d %d\n", &x[i].x, &x[i].y);
}

void punct_jos_stanga()
{
  P0=x[0];
  int poz=0;

  for(i=1;i<n;i++)
    if(x[i].y<P0.y) { poz=i; P0=x[i];}
    else if(x[i].y==P0.y)
	    if(x[i].x<P0.x) {  poz=i; P0=x[i];}
     point aux=x[0];
     x[0]=x[poz];
     x[poz]=aux;
	    
}

int isleft(point p0, point p1, point p2)
{
      return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}

bool operator <(const point &p1, const point &p2)
{
      int left=isleft(P0, p1, p2);
      if(left>=0) return true;
      return false; 
}
int cmp(point *p1, point *p2)
{
	int left=isleft(P0, *p1, *p2);
	if(left>0) return -1;
	if(left==0) return 0;
	if(left<0) return 1;

}
void sort()
{
	
	//sort(x, x+n);
qsort(x, n, sizeof(point), (int (*)(const void *, const void *))cmp);


}

void pune_in_stiva(point p)
{
      S[++t]=p;
}

void scoate_din_stiva()
{
  t--;
}


void graham()
{
      pune_in_stiva(x[0]);
      pune_in_stiva(x[1]);
      pune_in_stiva(x[2]);

      for(int i=3;i<n;i++)
	{
	  while(isleft(S[t-1], S[t], x[i])<0)scoate_din_stiva();
	  pune_in_stiva(x[i]);
	}
}

int verifica(point a, point b, point c)
{
	double r;
	r=((c.x-a.x)*(b.x-a.x)+(c.y-a.y)*(b.y-a.y))/(double)((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
	if(r>0 && r<1) return 1;
	return 0;
}

int main()
{
      freopen("dragon.out", "w", stdout);     
      citire();
      punct_jos_stanga();
 	sort();
	graham();

      int nr=0;
	  
      for(i=1;i<t;i++) if(verifica(S[i], S[i+1], pi)) nr++;
	  
      if(verifica(S[t], S[1], pi)) nr++;

     printf("%d\n", nr);
      return 0;
 }