Pagini recente » Cod sursa (job #2346106) | Cod sursa (job #661031) | Cod sursa (job #1533924) | Cod sursa (job #1667474) | Cod sursa (job #2535218)
#include <bits/stdc++.h>
#define ld long double
#define X first
#define Y second
#define punct pair<ld,ld>
using namespace std;
ifstream inf("infasuratoare.in");
ofstream outf("infasuratoare.out");
const int N = 120010;
int n,top;
pair<ld,ld> p[N];
ld det(punct a,punct b,punct c)
{
return a.X*b.Y+b.X*c.Y+c.X*a.Y-(a.X*c.Y+c.X*b.Y+b.X*a.Y);
}
bool crit(pair<ld,ld> a, pair<ld,ld> b)
{
ld aux=det(p[0],a,b);
if(aux>0.0)return true;
return false;
}
int main()
{
inf>>n;
for(int i=0; i<n; i++)
{
ld x, y;
inf>>x>>y;
p[i]=make_pair(x,y);
if(p[i]<p[0])
swap(p[0], p[i]);
}
sort(p+1, p+n, crit);
top=1;
for(int i=2;i<n;i++)
{
while(det(p[top-1],p[top],p[i])<0.0)
top--;
p[++top]=p[i];
}
outf<<top+1<<'\n';
for(int i=0;i<=top;i++)
outf<<fixed<<setprecision(12)<<p[i].X<<' '<<p[i].Y<<'\n';
return 0;
}