Pagini recente » Cod sursa (job #1063169) | Cod sursa (job #2392889) | Cod sursa (job #2649014) | Cod sursa (job #1042041) | Cod sursa (job #2110218)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<stack>
#include<iomanip>
#define INF 1100000000
#define DN 120100
using namespace std;
fstream fin("infasuratoare.in",ios::in),fout("infasuratoare.out",ios::out);
struct puncte
{
double x,y;
} v[DN];
int n,ind,ap[DN],lst;
double xm=INF,ym=INF;
puncte st[DN];
bool cmp(puncte a,puncte b)
{
if(a.x<b.x) return 1;
if(a.x==b.x && a.y<b.y) return 1;
return 0;
}
int det(puncte a,puncte b,puncte c)
{
double xx=0;
xx=a.x*b.y+b.x*c.y+a.y*c.x;
xx=xx-c.x*b.y-a.y*b.x-a.x*c.y;
if(xx>0) return 1;
if(xx<0) return -1;
return 0;
}
int main()
{
int i,k;
double x,y;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>x>>y;
v[i]={x,y};
}
sort(v+1,v+n+1,cmp);
st[1]=v[1];
lst=1;
for(i=2;i<=n;i++)
{
while(lst>1 && det(st[lst-1],st[lst],v[i]) > 0)
{
lst--;
}
lst++;
st[lst]=v[i];
}
k=lst;
for(i=n-1;i>=1;i--)
{
while(lst>k && det(st[lst-1],st[lst],v[i]) > 0)
{
lst--;
}
lst++;
st[lst]=v[i];
}
lst--;
fout<<lst<<"\n";
for(i=1;i<=lst;i++) fout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<"\n";
}