Pagini recente » Cod sursa (job #2065935) | Rating Saioc Vlad (vlad244) | Cod sursa (job #341754) | Cod sursa (job #723942) | Cod sursa (job #2029625)
#include <bits/stdc++.h>
#define MAX_N 120000
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct coord
{
long double x, y;
int i;
};
int n, rez;
coord v[MAX_N + 1];
coord cvx[MAX_N + 1];
coord mn;
long double poz(long double x)
{
if(x < 0.0D)
return -x;
return x;
}
const long double epsilon = 0.000000000001D;
void readFile()
{
f >> n;
mn = {2000000000.0D, 0.0D, 0};
int i;
for(i = 1; i <= n; i ++)
{
f >> v[i].x >> v[i].y;
v[i].i = i;
if(v[i].x < mn.x || (poz(v[i].x - mn.x) == epsilon && v[i].y < mn.y))
mn = v[i];
}
f.close();
}
long double ccw(coord a, coord b, coord c)
{
///x1 y1
///x2 y2
///x1*y2 - x2*y1;
return (a.x * b.y - b.x * a.y +
b.x * c.y - c.x * b.y +
c.x * a.y - a.x * c.y
)/2.0D;
}
struct cmp
{
bool operator () (coord a, coord b)
{
long double aria = ccw(mn, a, b);
return aria > 0.0D;
}
};
void solve()
{
if(mn.i != 1)
{
coord aux = v[1];
v[1] = mn;
v[mn.i] = aux;
}
sort(v + 2, v + n + 1, cmp());
rez = 2;
cvx[1] = v[1];
cvx[2] = v[2];
int i;
for(i = 3; i <= n; i ++)
{
while(rez >= 2 && ccw(cvx[rez - 1], cvx[rez], v[i]) < 0.0D)
rez --;
cvx[++ rez] = v[i];
}
}
void printFile()
{
g << rez << "\n";
int i;
for(i = 1; i <= rez; i ++)
g << fixed << setprecision(12) << cvx[i].x << " " << cvx[i].y << "\n";
g << "\n";
g.close();
}
int main()
{
readFile();
solve();
printFile();
return 0;
}