Pagini recente » Cod sursa (job #2605575) | Cod sursa (job #701713) | Cod sursa (job #955915) | Cod sursa (job #900833) | Cod sursa (job #690051)
Cod sursa(job #690051)
#include <cstdio>
#include <algorithm>
#define INF 100000000
#define Lmax 120000
using namespace std;
struct punct{
double x;
double y;
long double p;
}a[Lmax],st[Lmax];
int n;
int pi=0;
FILE *fin=freopen("infasuratoare.in","r",stdin);
FILE *fout=freopen("infasuratoare.out","w",stdout);
long double panta(int i)
{
if(a[i].x == a[pi].x)
return INF;
return(a[i].y-a[pi].y)/(a[i].x-a[pi].x);
}
void citire()
{
a[pi].x=INF;
a[pi].y=INF;
scanf("%d ",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&a[i].x,&a[i].y);
if(a[i].x<a[pi].x || a[i].x==a[pi].x && a[i].y<a[pi].y)
pi=i;
}
a[0]=a[pi];
a[pi]=a[n];
n--;
}
bool cmp(punct a, punct b)
{
if(a.p<b.p)
return true;
return false;
}
void fapante()
{
pi=0;
for(int i=1;i<=n;i++)
a[i].p=panta(i);
sort(a+1,a+n+1,cmp);
}
double det(punct a, punct b, punct c)
{
double D=a.x*b.y +c.x*a.y + b.x*c.y;
D-=(a.x*c.y+c.x*b.y + b.x*a.y);
if(D>=0)
return 1;
return 0;
}
int t=0;
void solve()
{
st[t++]=a[0];
st[t++]=a[1];
for(int i=2;i<=n;i++)
{
if(det(st[t-2],st[t-1],a[i]))
st[t++]=a[i];
else{
while(!det(st[t-2],st[t-1],a[i])){
st[--t]=a[i];
}
t++;
}
}
}
void afisare()
{
printf("%d\n",t);
for(int i=1;i<t;++i)
printf("%lf %lf\n",st[i].x,st[i].y);
printf("%lf %lf\n",st[0].x,st[0].y);
}
int main()
{
citire();
fapante();
solve();
afisare();
return 0;
}