Pagini recente » Cod sursa (job #221083) | Cod sursa (job #282967) | Cod sursa (job #1618121) | Cod sursa (job #2239725) | Cod sursa (job #582691)
Cod sursa(job #582691)
#include <cstdio>
#include <cstring>
#include <fstream>
#define INF 1.0*(0x3f3f3f3f)
#define Nmx 120005
using namespace std;
int n,pct,nr;
struct dat{
double x,y;
double panta;
};
dat a[Nmx],st[Nmx];
struct cmp
{
bool operator () (const dat &A,const dat &B)
{
if(A.panta==B.panta)
if(A.y==B.y)
return A.x<B.y;
else return A.y<B.y;
else return A.panta<B.panta;
}
};
void read()
{
double x,y;
scanf("%d",&n);
pct=1;
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&x,&y);
a[i].x=x;
a[i].y=y;
if(a[pct].x>x)
pct=i;
else if(a[pct].x==x && a[pct].y>y)
pct=i;
}
}
int calc(int x1,int y1,int x2,int y2)
{
if(x2-x1==0)
return INF;
return (y2-y1)/(x2-x1);
}
void prepro()
{
for(int i=1;i<=n;++i)
{
a[i].panta=-INF;
if(i!=pct)
a[i].panta=calc(a[pct].x,a[pct].y,a[i].x,a[i].y);
}
sort(a+1,a+n+1,cmp());
}
double semn(double x1,double y1,double x2,double y2,double x3,double y3)
{
return x1*y2+x2*y3+x3*y1-x3*y2-x1*y3-x2*y1;
}
void solve()
{
st[++nr]=a[1];
st[++nr]=a[2];
for(int i=3;i<=n;++i)
{
while(nr>=2&&semn(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,a[i].x,a[i].y)<0)
--nr;
st[++nr]=a[i];
}
printf("%d\n",nr);
for(int i=1;i<=nr;++i)
printf("%.6lf %.6lf\n",st[i].x,st[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
prepro();
solve();
return 0;
}