Pagini recente » Cod sursa (job #2865556) | Cod sursa (job #1231695) | Cod sursa (job #637423) | Cod sursa (job #2169229) | Cod sursa (job #3246983)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
double x,y;
bool t;
}pct[120001];
vector <Punct> s;
bool sortpct(Punct a,Punct b)
{
return(a.x<b.x || (a.x==b.x && a.y<b.y));
}
double Arie(Punct a,Punct b,Punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
int main()
{
int n;
double x,y;
fin>>n;
for(int i=0;i<n;i++)
{
fin>>x>>y;
pct[i]={x,y};
}
sort(pct,pct+n,sortpct);
for(int i=1;i<n-1;i++)
{
double arie=Arie(pct[0],pct[n-1],pct[i]);
pct[i].t=(arie>0);
}
for(int i=0;i<n;i++)
{
if(pct[i].t)
continue;
while(s.size()>=2)
{
double arie=Arie(s[s.size()-2],s[s.size()-1],pct[i]);
if(arie<0)
s.pop_back();
else break;
}
s.push_back(pct[i]);
}
int size0=s.size()-1;
pct[n-1].t=pct[0].t=1;
for(int i=n-2;i>=0;i--)
{
if(!pct[i].t)
continue;
while(s.size()-size0>=2)
{
double arie=Arie(s[s.size()-1],s[s.size()-2],pct[i]);
if(arie>0)
s.pop_back();
else break;
}
s.push_back(pct[i]);
}
s.pop_back();
fout<<s.size()<<'\n'<<fixed<<setprecision(6);
for(int i=0;i<s.size();i++)
fout<<s[i].x<<" "<<s[i].y<<'\n';
return 0;
}