Pagini recente » Cod sursa (job #1805108) | Cod sursa (job #961900) | Cod sursa (job #2959451) | Cod sursa (job #110527) | Cod sursa (job #1907049)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
double x,y;
};
vector<Point> v,h;
int N;
void Read();
double det(Point a, Point b, Point c);
bool comparePoints(Point a, Point b);
bool compareAngles(Point a, Point b);
void ConvexHull();
int main()
{
Read();
ConvexHull();
fout<<fixed;
fout<<h.size()<<'\n';
for(int i=0;i<h.size();++i)
fout<<setprecision(9)<<h[i].x<<" "<<h[i].y<<'\n';
return 0;
}
void Read()
{
fin>>N;
v=vector<Point>(N+1);
for(int i=0;i<N;++i)
fin>>v[i].x>>v[i].y;
}
double det(Point a, Point b, Point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool comparePoints(Point a, Point b)
{
return (a.x<b.x)||(a.x==b.x)&&(a.y<b.y);
}
bool compareAngles(Point a, Point b)
{
return det(v[0],a,b)<0;
}
void ConvexHull()
{
swap(v[0],*min_element(v.begin(),v.end(),comparePoints));
sort(v.begin()+1, v.end(),compareAngles);
h.push_back(v[0]);
h.push_back(v[1]);
for(int i=2;i<v.size();++i)
{
while(h.size()>1 && det(*(h.end()-1), *(h.end()-2), v[0])>0)
{h.erase(h.end()-1);}
h.push_back(v[i]);
}
reverse(h.begin(),h.end());
}