Pagini recente » Cod sursa (job #1573408) | Cod sursa (job #1015372) | Cod sursa (job #2376790) | Cod sursa (job #2470168) | Cod sursa (job #3359386)
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
double x;
double y;
};
double crossProduct(Point A, Point B, Point C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int main()
{
int N;
fin>>N;
fout<<fixed<<setprecision(15);
vector<Point> points(N);
for (int i=0; i<N; i++)
{
fin>>points[i].x>>points[i].y;
}
sort(points.begin(),points.end(),
[](Point a, Point b)
{
if (a.x != b.x)
return a.x<b.x;
return a.y<b.y;
}
);
vector<Point> hull;
for (int i=0; i<N; i++)
{
if (hull.size()>=2)
while(hull.size()>=2 && crossProduct(hull[hull.size()-2],hull[hull.size()-1],points[i])<=0)
hull.pop_back();
hull.push_back(points[i]);
}
int t=hull.size()+1;
for (int i=N-2; i>=0; i--)
{
if (hull.size()>=t)
while(hull.size()>=t && crossProduct(hull[hull.size()-2],hull[hull.size()-1],points[i])<=0)
hull.pop_back();
hull.push_back(points[i]);
}
hull.pop_back();
fout<<hull.size()<<endl;
for (int i=0; i<hull.size(); i++)
fout<<hull[i].x<<" "<<hull[i].y<<endl;
return 0;
}