Pagini recente » Cod sursa (job #1114845) | Simulare 51b | Cod sursa (job #1031043) | Cod sursa (job #2022308) | Cod sursa (job #261756)
Cod sursa(job #261756)
#include<cstdio>
#include<algorithm>
#define MX 120001
#define oo 100000001
#include<vector>
using namespace std;
struct pct
{
double x,y;
long double panta;
bool operator!=(pct a)
{
return x==a.x&&y==a.y?0:1;
}
bool operator==(pct a)
{
return x==a.x&&y==a.y?1:0;
}
};
pct a[MX],mn;
long n,k=1;
pct s[MX];
long double sm(pct a,pct b, pct c)
{
return (long double)(a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y);
}
void rd()
{
mn.x=mn.y=oo;
scanf("%ld",&n);
for(long i=1;i<=n;i++)
{
float x,y;
scanf("%f%f",&x,&y);
a[i].x=x,a[i].y=y;
if(mn.x>a[i].x)
mn=a[i];
else if(mn.x==a[i].x&&mn.y>a[i].y)
mn=a[i];
}
}
bool cmp(pct a,pct b)
{
return (long double)(a.y-mn.y)*(b.x-mn.x)<(long double)(a.x-mn.x)*(b.y-mn.y);
}
void go()
{
s[1]=mn;
for(long i=1;i<=n;i++)
if(a[i]!=mn)
{
long double x=sm(s[k-1],s[k],a[i]);
while(k>=2&&x<0)
{
k--;
x=sm(s[k-1],s[k],a[i]);
}
s[++k]=a[i];
}
}
void afisare()
{
printf("%ld\n",k);
for(long i=1;i<=k;i++)
printf("%f %f\n",s[i].x,s[i].y);
}
void kk1()
{
for(long i=1;i<=n;i++)
a[i].panta=a[i].x-mn.x==0?0:(a[i].y-mn.y)/(a[i].x-mn.x);
}
bool ckk(pct a,pct b)
{
return a.panta<b.panta;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
rd();
kk1();
sort(a+1,a+n+1,ckk);
//sort(a+1,a+n+1,cmp);
go();
afisare();
return 0;
}