Pagini recente » Cod sursa (job #2790002) | Cod sursa (job #2630188) | Cod sursa (job #1480490) | Cod sursa (job #1932498) | Cod sursa (job #2426486)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
#define INF 1500000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,i;
pair<double, double> v[120005],sol[120005];
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cmp(pair<double, double> a, pair<double, double> b)
{
double d = det(make_pair(0, 0), a, b);
if (d == 0)
return a.x*a.x+a.y*a.y > b.x*b.x+b.y*b.y;
else
return d > 0;
}
int main()
{
fin >> n;
for (i=1; i<=n; i++)
fin >> v[i].x >> v[i].y;
int punctmin = 0; double minimy = INF; double minimx = INF;
for (i=1; i<=n; i++)
if (v[i].y < minimy)
{
minimy = v[i].y;
minimx = v[i].x;
punctmin = i;
}
else
if (v[i].y == minimy)
if (v[i].x < minimx)
{
minimx = v[i].x;
punctmin = i;
}
double xx = v[punctmin].x; double yy = v[punctmin].y;
for (i=1; i<=n; i++)
{
v[i].x -= xx;
v[i].y -= yy;
}
swap(v[1], v[punctmin]);
sort(v+2, v+n+1, cmp);
int ind = 0;
for (i=3; i<=n; i++)
if (det(v[1], v[2], v[i]) != 0)
{
ind = i;
break;
}
ind--;
if (ind > 2)
for (i=2; i<=(ind+1)/2; i++)
swap(v[i], v[ind-i+2]);
sol[1] = v[1];
sol[2] = v[2];
int k = 2;
for (i=3; i<=n; i++)
{
while (k >= 2 && det(sol[k-1], sol[k], v[i]) < 0)
k--;
sol[++k] = v[i];
}
fout << k << "\n";
for (i=1; i<=k; i++)
{
fout << setprecision(6) << fixed << sol[i].x+xx << " ";
fout << setprecision(6) << fixed << sol[i].y+yy << "\n";
}
return 0;
}