Pagini recente » Cod sursa (job #1634016) | Cod sursa (job #2126783) | Cod sursa (job #1916127) | Cod sursa (job #2494702) | Cod sursa (job #3269990)
#include <fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x,y;
bool operator == (point b)
{
return x==b.x&&y==b.y;
}
} v[120005],start;
int n;
double 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 comp(point a,point b)
{
if(a==start)
return true;
if(b==start)
return false;
double val=aria(start,a,b);
if(val==0)
return a.x<b.x;
return val>0;
}
int main()
{
start={2e9,2e9};
fin>>n;
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++)
{
point p=v[i];
while(sol.size()>=2)
{
int lg=(int)sol.size();
point a=sol[lg-2];
point b=sol[lg-1];
if(aria(a,b,p)<0)
sol.pop_back();
else
break;
}
sol.push_back(p);
}
fout<<sol.size()<<'\n';
for(point p:sol)
fout<<fixed<<setprecision(12)<<p.x<<' '<<p.y<<'\n';
return 0;
}