Pagini recente » Cod sursa (job #1755523) | Cod sursa (job #2542774) | Cod sursa (job #119775) | Cod sursa (job #1663511) | Cod sursa (job #2553130)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,pozstart;
struct point
{
double x;
double y;
};
point v[200001],start,st[200001];
bool comp(point a,point b)
{
a.x-=start.x;
a.y-=start.y;
b.x-=start.x;
b.y-=start.y;
if(a.x*b.y<a.y*b.x)
return 1;
else if(a.x*b.y==a.y*b.x&&a.x<b.x)
return 1;
return 0;
}
double aria(point a,point b,point c)
{
a.x-=c.x;
a.y-=c.y;
b.x-=c.x;
b.y-=c.y;
return a.x*b.y-a.y*b.x;
}
void infasoara()
{
start.x=1000000000;
start.y=1000000000;
pozstart=0;
for(int i=1;i<=n;i++)
{
if(v[i].x<start.x)
{
start=v[i];
pozstart=i;
}
else if(v[i].x==start.x&&v[i].y<start.y)
{
start=v[i];
pozstart=i;
}
}
for(int i=1;i<=n;i++)
if(i==pozstart)
{
for(int j=i+1;j<=n;j++)
v[j-1]=v[j];
break;
}
n--;
sort(v+1,v+n+1,comp);
st[1]=start;
st[2]=v[1];
int lgst=2;
for(int i=2;i<=n;i++)
{
while(aria(st[lgst-1],st[lgst],v[i])>0&&lgst>2)
lgst--;
st[++lgst]=v[i];
}
fout<<lgst<<'\n';
for(int i=lgst;i>=1;i--)
fout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<'\n';
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
infasoara();
return 0;
}