Pagini recente » Cod sursa (job #1977688) | Cod sursa (job #623626) | Cod sursa (job #1263012) | Cod sursa (job #42135) | Cod sursa (job #1686555)
#include <bits/stdc++.h>
using namespace std;
#define point pair < double , double >
#define x first
#define y second
const int nmax = 120009;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i;
bool compare(point , point);
class ConvexHull
{
public :
point v[nmax] , ch[nmax];
int n , S;
double cross(point A , point B , point C)
{
double a , b , c;
a = A.y - B.y;
b = B.x - A.x;
c = A.x * B.y - B.x * A.y;
return a * C.x + b * C.y + c;
}
void work()
{
int i;
for (i = 2 ; i <= n ; ++i)
if (v[i] < v[1]) swap(v[i] , v[1]);
sort(v + 2 , v + n + 1 , compare);
S = 0;
ch[++S] = v[S];
ch[++S] = v[S];
for (i = 3 ; i <= n ; ++i)
{
while (2 <= S && cross(ch[S - 1] , ch[S] , v[i]) > 0) S--;
ch[++S] = v[i];
}
}
} solve;
bool compare(point A , point B)
{
return solve.cross(solve.v[1] , A , B) < 0;
}
int main()
{
fin >> solve.n;
for (i = 1 ; i <= solve.n ; ++i)
{
fin >> solve.v[i].x;
fin >> solve.v[i].y;
}
solve.work();
fout << solve.S << '\n';
for (i = 1 ; i <= solve.S ; ++i)
{
fout << fixed << setprecision(9) << solve.ch[i].x << " ";
fout << fixed << setprecision(9) << solve.ch[i].y << '\n';
}
return 0;
}