Pagini recente » Cod sursa (job #2905144) | Cod sursa (job #951700) | Cod sursa (job #578811) | Cod sursa (job #2424453) | Cod sursa (job #2339807)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int N = 120005;
struct Point
{
double x,y;
} v[N],hull[N];
double sqrDist(Point a, Point b)
{
double dx = a.x-b.x, dy = a.y-b.y;
return dx*dx+dy*dy;
}
int orientation(Point a, Point b, Point c)
{
double val = (b.y-a.y)*(c.x-b.x)-(c.y-b.y)*(b.x-a.x);
if (val<0)
return -1;
if (val>0)
return 1;
return 0;
}
Point pivot;
bool comp(Point a, Point b)
{
int k = orientation(pivot,a,b);
if (!k)
return sqrDist(a,pivot)<sqrDist(b,pivot);
return (k == -1);
}
int main()
{
int n;
in >> n;
for (int i = 1; i<=n; i++)
in >> v[i].x >> v[i].y;
pivot = v[1];
for (int i = 2; i<=n; i++)
if (v[i].y<pivot.y || (v[i].y == pivot.y && v[i].x<pivot.x))
pivot = v[i];
v[1] = pivot;
sort(v+2,v+n+1,comp);
hull[1] = v[1]; hull[2] = v[2];
int head = 2;
for (int i = 3; i<=n; i++)
{
while (head>=2 && orientation(hull[head-1],hull[head],v[i])!=-1)
head--;
hull[++head] = v[i];
}
out << head << "\n";
for (int i = 1; i<=head; i++)
out << fixed << setprecision(10) << hull[i].x << " " << hull[i].y << "\n";
}