Pagini recente » Cod sursa (job #1333633) | Cod sursa (job #1832649) | Cod sursa (job #1544123) | Cod sursa (job #2108981) | Cod sursa (job #1837480)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <fstream>
using namespace std;
#define MAXN 120003
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
}P[MAXN];
double det(punct a,punct b, punct c){
return ((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
}
bool cmp(punct a,punct b)
{
return det(P[1],a,b)>0;
}
int n,xmini=2e9,ymini=2e9,p_mini,st[MAXN],vf;
int main()
{
f>>n;
for(int i=1;i<=n;i++)
f>>P[i].x>>P[i].y;
for(int i=1;i<=n;i++)
if(P[i].x<xmini)xmini=P[i].x;
for(int i=1;i<=n;i++)
if(P[i].x==xmini&&P[i].y<ymini) {ymini=P[i].y;p_mini=i;}
swap(P[1],P[p_mini]);
sort(P+2,P+n+1,cmp);
//for(int i=1;i<=n;i++) g<<fixed<<setprecision(6)<<P[i].x<<' '<<P[i].y<<'\n';
P[n+1]=P[1];
st[1]=1;
st[2]=2;
vf=2;
for(int i=3;i<=n+1;i++)
{
while(vf>1&&det(P[st[vf-1]],P[st[vf]],P[i])<=0)
vf--;
st[++vf]=i;
}
g<<vf-1<<'\n';
for(int i=2;i<=vf;i++)
g<<fixed<<setprecision(6)<<P[st[i]].x<<' '<<P[st[i]].y<<'\n';
return 0;
}