Pagini recente » Cod sursa (job #2883407) | Cod sursa (job #1493983) | Cod sursa (job #1258822) | Cod sursa (job #1210600) | Cod sursa (job #2450330)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <iomanip>
using namespace std;
typedef long double ld;
const int N=120000+7;
int n;
struct pt
{
ld x;
ld y;
};
ld tr(pt a,pt b)
{
return (a.x-b.x)*(a.y+b.y);
}
ld ar(pt a,pt b,pt c)
{
return tr(a,b)+tr(b,c)+tr(c,a);
}
pt mn(pt a,pt b)
{
if(a.x<b.x)
return a;
if(b.x<a.x)
return b;
if(a.y<b.y)
return a;
return b;
}
pt loft;
bool cmp(pt a,pt b)
{
if(a.x==loft.x && a.y==loft.y) return 1;
if(b.x==loft.x && b.y==loft.y) return 0;
return (ar(loft,a,b)>0);
}
pt st[N];
int top;
void baga(pt a)
{
while(top>=2 && (ar(st[top-1],st[top],a)<=0))
top--;
st[++top]=a;
}
pt a[N];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
loft=a[1];
for(int i=2;i<=n;i++)
loft=mn(loft,a[i]);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
baga(a[i]);
baga(a[1]);
top--;
cout<<top<<"\n";
for(int i=1;i<=top;i++)
cout<<fixed<<setprecision(6)<<a[i].x<<" "<<a[i].y<<"\n";
return 0;
}