Pagini recente » Cod sursa (job #1867481) | Cod sursa (job #602924) | Cod sursa (job #1873290) | Cod sursa (job #651119) | Cod sursa (job #3268079)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i,k=0;
struct number
{
double x,y;
} v[120005],s[120005];
void read()
{
fin>>n;
for(i=1; i<=n; i++)
fin>>v[i].x>>v[i].y;
}
double comp(number a,number b)
{
return ((a.y<b.y)||(a.y==b.y&&a.x<b.x));
}
double comp2(number a,number b)
{
return ((double)(a.y-v[1].y)*(b.x-v[1].x)<(double)(b.y-v[1].y)*(a.x-v[1].x));
}
double determinant(double xa,double ya,double xb,double yb,double xc,double yc)
{
return (xb*yc+xc*ya+xa*yb-xb*ya-xc*yb-xa*yc);
}
void solve()
{
sort(v+1,v+n+1,comp);
s[++k].x=v[1].x;
s[k].y=v[1].y;
sort(v+2,v+n+1,comp2);
s[++k].x=v[2].x;
s[k].y=v[2].y;
for(i=3; i<=n; i++)
{
s[++k].x=v[i].x;s[k].y=v[i].y;
double d=determinant(s[k-2].x,s[k-2].y,s[k-1].x,s[k-1].y,s[k].x,s[k].y);
while(k>2&&d<0)
{
k--;
s[k].x=v[i].x;s[k].y=v[i].y;
d=determinant(s[k-2].x,s[k-2].y,s[k-1].x,s[k-1].y,v[i].x,v[i].y);
}
}
}
void afis()
{
fout<<k<<'\n';
for(i=1; i<=k; i++)
fout<<fixed<<setprecision(12)<<s[i].x<<" "<<setprecision(12)<<s[i].y<<'\n';
}
int main()
{
read();
solve();
afis();
return 0;
}