Pagini recente » Cod sursa (job #1580081) | Cod sursa (job #2455469) | Cod sursa (job #1983911) | Cod sursa (job #2591595) | Cod sursa (job #2865)
Cod sursa(job #2865)
#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;
}