Pagini recente » Cod sursa (job #1796193) | Cod sursa (job #1033972) | Cod sursa (job #2289482) | Cod sursa (job #1009866) | Cod sursa (job #1668487)
//GRAHAM SCAN
#include<fstream>
#include<vector>
#include<iomanip>
#include<algorithm>
#include<stack>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int N;
typedef pair<double, double> POINT2D;
#define x first
#define y second
POINT2D v[120010];
POINT2D vec[120010];
int nr = 0;
int el = 1;
double inline crossprod2D(const POINT2D &p1, const POINT2D &p2, const POINT2D &p3)
{
return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x);
}
bool compare(const POINT2D &p1, const POINT2D &p2)
{
if (crossprod2D(v[1],p1,p2) > 0)
return 1;
else
return 0;
}
int main()
{
in >> N;
for (int i = 1;i <= N;++i)
in >> v[i].x >> v[i].y;
double y_min = v[1].y;
el = 1;
for (int i = 2;i <= N;++i)
if (v[i].y < y_min)
{
el = i;
y_min = v[i].y;
}
swap(v[el], v[1]);
sort(v + 2, v + N + 1, compare);
vec[++nr] = v[1];
vec[++nr] = v[2];
for (int i = 3;i <= N;++i)
{
while (crossprod2D(vec[nr - 1], vec[nr], v[i]) < 0)
--nr;
vec[++nr] = v[i];
}
while (crossprod2D(vec[nr - 1], vec[nr], v[1]) < 0)
--nr;
out << nr << '\n';
for (int i = 1;i <= nr;++i)
out <<setprecision(12)<<fixed<< vec[i].x << " " << vec[i].y << '\n';
}