Pagini recente » Cod sursa (job #163339) | Cod sursa (job #1185228) | Cod sursa (job #1440018) | Cod sursa (job #1663002) | Cod sursa (job #3216078)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
const ld INF=2e9;
int n;
struct point
{
ld x,y;
bool operator == (point a)
{
return x==a.x&&y==a.y;
}
} v[120005];
point start;
ld 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;
}
bool comp(point a,point b)
{
if(a==start)
return 1;
if(b==start)
return 0;
ld val=aria(start,a,b);
if(val==0)
return a.x<b.x;
return val>0;
}
int main()
{
ios_base::sync_with_stdio(false);
fin.tie(0);
fin>>n;
start={INF,INF};
for(int i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].x<start.x)
start=v[i];
else if(v[i].x==start.x)
start.y=min(start.y,v[i].y);
}
sort(v+1,v+n+1,comp);
vector<point> sol;
for(int i=1;i<=n;i++)
{
if(sol.size()<2)
{
sol.push_back(v[i]);
continue;
}
while(sol.size()>=2)
{
int lg=sol.size();
point a=sol[lg-2];
point b=sol[lg-1];
point c=v[i];
if(aria(a,b,c)<0)
sol.pop_back();
else
break;
}
sol.push_back(v[i]);
}
fout<<sol.size()<<'\n';
reverse(sol.begin(),sol.end());
for(auto i:sol)
fout<<fixed<<setprecision(12)<<i.x<<' '<<i.y<<'\n';
return 0;
}