Pagini recente » Cod sursa (job #1588674) | Cod sursa (job #3155289) | Cod sursa (job #1158661) | Cod sursa (job #2695290) | Cod sursa (job #3217333)
#include <bits/stdc++.h>
#define MAX 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct str
{
double x,y;
}pct[MAX];
double det(str a,str b,str c)
{
double x1=a.x;
double y1=a.y;
double x2=b.x;
double y2=b.y;
double x3=c.x;
double y3=c.y;
return x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3;
}
bool cmp(str a,str b)
{
return det(pct[1],a,b)<0;
}
str stv[MAX];
int main()
{
int n;
fin>>n;
int i;
for(i=1;i<=n;++i)
fin>>pct[i].x>>pct[i].y;
for(i=2;i<=n;++i)
if(pct[i].x<pct[1].x || (pct[i].x==pct[1].x && pct[i].y<pct[1].y))
swap(pct[i],pct[1]);
sort(pct+2,pct+n+1,cmp);
int vf=0;
for(i=1;i<=n;++i)
{
while(vf>1 && det(stv[vf-1],stv[vf],pct[i])>0)
--vf;
stv[++vf]=pct[i];
}
fout<<vf<<'\n';
for(i=vf;i;--i)
fout<<fixed<<setprecision(6)<<stv[i].x<<' '<<stv[i].y<<'\n';
return 0;
}