Pagini recente » Cod sursa (job #2972171) | Cod sursa (job #304333) | Cod sursa (job #822859) | Cod sursa (job #135892) | Cod sursa (job #2987602)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <vector>
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
const int NMAX=12e4+5;
struct coords{
long double x;
long double y;
}v[NMAX];
vector<coords>convexhull;
long double area(coords a,coords b,coords c)
{
return a.x*b.y+a.y*c.x+b.x*c.y-b.y*c.x-a.y*b.x-a.x*c.y;
}
bool cmp(coords a,coords b)
{
if(area(v[1],a,b)>=0)
return false;
return true;
}
int main()
{
int n,i,j,ind=1;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
for(i=2;i<=n;i++)
{
if(v[ind].y>=v[i].y)
{
if(v[ind].y>v[i].y)
ind=i;
else if(v[ind].y==v[i].y && v[ind].x<v[i].x)
ind=i;
}
}
swap(v[1],v[ind]);
sort(v+2,v+n+1,cmp);
convexhull.push_back(v[1]);
convexhull.push_back(v[2]);
for(i=3;i<=n;i++)
{
while(convexhull.size()>=2 && area(convexhull[convexhull.size()-2],convexhull[convexhull.size()-1],v[i])>=0)
convexhull.pop_back();
convexhull.push_back(v[i]);
}
fout<<convexhull.size()<<"\n";
for(auto i:convexhull)
fout<<fixed<<setprecision(12)<<i.x<<" "<<i.y<<"\n";
return 0;
}