Pagini recente » Cod sursa (job #2051785) | Cod sursa (job #1732015) | Cod sursa (job #2034635) | Cod sursa (job #87232) | Cod sursa (job #1644972)
//Conex Hull Andrew's Algorithm
//Complexity: O(n*logn)
//Implementation time:
#include <fstream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double epsilon = 1e-12;
typedef pair<double , double> point;
point points[120001];
bool viz[120001];
int stiva[120001];
int n , top;
double crossProduct(point O, point A, point B) {
return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}
int main()
{
f >> n;
for(int i = 1; i <= n; ++i) f >> points[i].first >> points[i].second;
sort(points + 1 , points + n + 1);
for(int i = 1; i <= n; i++)
{
if(viz[i]) continue;
while(top >= 2 && crossProduct(points[stiva[top - 1]] , points[stiva[top]] , points[i]) < epsilon)
viz[stiva[top--]] = false;
stiva[++top] = i;
viz[i] = true;
}
for(int i = n - 1 , t = top + 1; i >= 1; i--)
{
if(viz[i]) continue;
while(top >= t && crossProduct(points[stiva[top - 1]] , points[stiva[top]] , points[i]) < epsilon)
viz[stiva[top--]] = false;
stiva[++top] = i;
viz[i] == true;
}
g << top << "\n";
g << fixed << setprecision(6);
for(int i = 1; i <= top; i++) g << points[stiva[i]].first << " " << points[stiva[i]].second << "\n";
return 0;
}