Pagini recente » Cod sursa (job #2701754) | Cod sursa (job #1632400) | Cod sursa (job #225101) | Cod sursa (job #2176726) | Cod sursa (job #3029934)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
int n;
struct point
{
ld x,y;
} v[120005];
point start;
bool byx(point a, point b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
ld aria(point a, point b,point c)
{
a.x-=c.x;
b.x-=c.x;
a.y-=c.y;
b.y-=c.y;
return a.x*b.y-a.y*b.x;
}
bool egal(point a,point b)
{
return a.x==b.x&&a.y==b.y;
}
bool comp(point a,point b)
{
/*a.x-=start.x;
a.y-=start.y;
b.x-=start.x;
b.y-=start.y;*/
if(egal(a,start))
return 1;
if(egal(b,start))
return 0;
if(aria(a,b,start)<0)
return 0;
if(aria(a,b,start)>0)
return 1;
if(aria(a,b,start)==0)
return a.x<b.x;
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,byx);
start=v[1];
sort(v+1,v+n+1,comp);
vector<point> s;
s.push_back(start);
for(int i=2;i<=n;i++)
{
while(s.size()>=2)
{
int lg=s.size();
if(aria(v[i],s[lg-1],s[lg-2])>0)
s.pop_back();
else
break;
}
s.push_back(v[i]);
}
fout<<s.size()<<'\n';
fout<<fixed<<setprecision(12);
for(auto i:s)
fout<<i.x<<' '<<i.y<<'\n';
return 0;
}