Pagini recente » Cod sursa (job #786804) | Cod sursa (job #998702) | Cod sursa (job #799834) | Cod sursa (job #789398) | Cod sursa (job #2295733)
#include <bits/stdc++.h>
using namespace std;
class Dot
{
public:
double x,y;
double angle;
private:
/// functions
public:
void setAngle(Dot a)
{
if (a.x != x)
angle = (a.y - y) / (a.x - x);
else
angle = numeric_limits<double>::infinity();
}
Dot()
{}
Dot(int a, int b)
{
x=a;
y=b;
}
~Dot()
{}
private:
};
bool comp(Dot a, Dot b)
{
return a.angle < b.angle;
}
double det(Dot a1, Dot a2, Dot a3)
{
return (a2.x - a1.x) * (a3.y - a1.y) - (a2.y - a1.y) * (a3.x - a1.x);
}
vector <Dot> makeConvexHull(vector <Dot> &dots, int n)
{
vector <Dot> stk;
stk.push_back(dots[0]);
stk.push_back(dots[1]);
for(int i = 2; i < n; i++)
{
while(det(stk[stk.size() - 2], stk[stk.size() - 1], dots[i]) < 0)
{
stk.pop_back();
}
stk.push_back(dots[i]);
}
return stk;
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main()
{
int start_index = 0;
int n;
double x, y;
fin>>n;
vector <Dot> dots(n);
for(int i = 0; i < n; i++)
{
fin>>x>>y;
dots[i] = Dot(x, y);
if(dots[i].x <= dots[start_index].x)
{
if(dots[i].x == dots[start_index].x && dots[i].y < dots[start_index].y)
start_index = i;
else if(dots[i].x < dots[start_index].x)
start_index = i;
}
}
swap(dots[0], dots[start_index]);
for(int i = 1; i < n; i++)
dots[i].setAngle(dots[0]);
sort(dots.begin() + 1, dots.end(), comp);
vector <Dot> ans = makeConvexHull(dots, n);
fout<<ans.size()<<'\n';
for(unsigned i = 0; i < ans.size(); i++)
fout<<setprecision(6)<<fixed<<ans[i].x<<' '<<ans[i].y<<'\n';
return 0;
}