Pagini recente » Cod sursa (job #3141709) | Cod sursa (job #1779292) | Cod sursa (job #1987379) | Cod sursa (job #571102) | Cod sursa (job #3215423)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct Punct
{
long double x , y;
}a[120001];
vector <Punct> hull;
int N;
long double up (Punct X)
{
return acos((1.0 * X.x) / sqrt(X.x * X.x + X.y * X.y));
}
bool cmp (Punct A , Punct B)
{
return up (A) < up (B);
}
int Orientation (Punct A , Punct B , Punct C)
{
long double t = (B.y - A.y) * (C.x - B.x) - (C.y - B.y) * (B.x - A.x);
if(t == 0)
return 0; /// Coliniare
else if(t > 0)
return 1; /// inv. trig
return 2;
}
int main()
{
fin >> N;
for (int i = 1; i <= N; ++i)
fin >> a[i].x >> a[i].y;
/// Aleg punctul cu ordonata minima
int p = 1;
for (int i = 2; i <= N; ++i)
if(a[i].x < a[p].x || (a[i].x == a[p].x && a[i].y < a[p].y))
p = i;
/// Realizez infasurarea
int currInd = p;
do
{
hull.push_back(a[currInd]);
int ind;
if(currInd == N)
ind = 1;
else
ind = currInd + 1;
for (int i = 1; i <= N; ++i)
if(Orientation(a[currInd] , a[i] , a[ind]) == 2) /// Punctul i realiz. o intoarecere mai mare
ind = i;
currInd = ind;
}while(currInd != p);
fout << fixed << setprecision(12);
fout << hull.size() << "\n";
sort (hull.begin() , hull.end() , cmp);
for (int i = 0; i < hull.size(); ++i)
fout << hull[i].x << " " << hull[i].y << "\n";
}