Pagini recente » Cod sursa (job #2875008) | Cod sursa (job #2473574) | Diferente pentru schimbare-borland/argumentatie intre reviziile 27 si 15 | Monitorul de evaluare | Cod sursa (job #2260014)
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<double,double> punct;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,top;
punct v[120001];
double det(punct A,punct B,punct C)
{
return A.X*B.Y+B.X*C.Y+C.X*A.Y-(A.Y*B.X+B.Y*C.X+C.Y*A.X);
}
bool cmp(punct A,punct B)
{
return det(v[0],A,B)>0;
}
int main()
{
f>>n;
for(i=0; i<n; i++)
{
double x,y;
f>>x>>y;
v[i]=make_pair(x,y);
if(v[i]<=v[0])
swap(v[i],v[0]);
}
sort(v+1,v+n,cmp);
top=1;
for(i=2;i<n;i++)
{
while(det(v[top-1],v[top],v[i])<=0)
top--;
v[++top]=v[i];
}
g<<top+1<<'\n';
for(i=0;i<=top;i++)
g<<fixed<<setprecision(8)<<v[i].X<<' '<<v[i].Y<<'\n';
return 0;
}