Pagini recente » Cod sursa (job #2487799) | Cod sursa (job #933134) | Cod sursa (job #651138) | Cod sursa (job #1238235) | Cod sursa (job #656049)
Cod sursa(job #656049)
#include <stdio.h>
#include <algorithm>
#define Nmax 120001
#define inf 0xffffffff
using namespace std;
int h,n = 2,poz;
FILE *c,*d;
struct punct
{
float x, y, p;
} a[Nmax],s[Nmax],x;
bool cmp(punct a, punct b)
{
if (a.p>b.p)
return false;
return true;
}
void citire()
{
int i;
x.x = x.y = inf;
fscanf (c,"%d ", &h);
for (i=0;i<h;++i)
{
fscanf (c,"%f %f ", &a[i].x, &a[i].y);
if (a[i].x<x.x||a[i].x==x.x&&a[i].y<x.y)
{
x.x = a[i].x;
x.y = a[i].y;
poz = i;
}
}
a[poz]=a[h-1];
--h;
}
void afisare()
{
int i;
fprintf (d,"%d\n", n);
for (i=0;i<n;++i)
fprintf (d,"%f %f\n", s[i].x, s[i].y);
}
void panta()
{
int i;
for (i=0;i<h;++i)
if (a[i].x==x.x)
a[i].p=inf;
else
a[i].p=(a[i].y-x.y)/(a[i].x-x.x);
}
bool determinant(punct a,punct b,punct c)
{
double det=a.x*b.y+a.y*c.x+b.x*c.y-a.y*b.x-b.y*c.x-c.y*a.x;
if (det>=0)
return 1;
return 0;
}
void infasuratoare()
{
int i;
s[0]=x;
s[1]=a[0];
for(i=1;i<h;++i)
if (determinant(s[n-2],s[n-1],a[i]))
s[n++]=a[i];
else
{
while(determinant(s[n-2],s[n-1],a[i])==0)
s[--n]=a[i];
++n;
}
}
int main()
{
c=fopen("infasuratoare.in","r");
d=fopen("infasuratoare.out","w");
citire();
panta();
sort(a,a+h,cmp);
infasuratoare();
afisare();
fclose(c);
fclose(d);
return 0;
}