Pagini recente » Cod sursa (job #292012) | Cod sursa (job #873307) | Cod sursa (job #1321171) | Cod sursa (job #2285230) | Cod sursa (job #1335107)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define inf 0x3f3f3f3f
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 120009;
struct punct {
double x, y;
}v[MAXN];
int N, top;
punct stack[MAXN];
inline double CrossProduct(punct A, punct B, punct C) {
return ( double ) A.x*B.y + B.x*C.y + C.x*A.y - A.y*B.x - B.y*C.x - C.y*A.x;
}
bool cmp(punct i,punct j)
{
return atan2(i.y-v[0].y,i.x-v[0].x)<atan2(j.y-v[0].y,j.x-v[0].x);
}
void Read() {
fin >> N;
int poz = 0;
for (int i = 0; i < N; ++i) {
fin >> v[i].x >> v[i].y;
if (v[poz].y > v[i].y)//saves the lowest point, or in case of equality, the most right one
poz = i;
if (v[poz].y == v[i].y && v[poz].x > v[i].x)
poz = i;
}
swap(v[0], v[poz]);
}
void ConvexHull() {
//sorts the points increasingly according to the slopes between the fixed point and another point
sort(v + 1, v + N, cmp);
stack[0] = v[0];
stack[1] = v[1];
top = 1;
for (int i = 2; i < N; ++i) {
while (top >= 1 && CrossProduct(stack[top - 1], stack[top], v[i]) < 0)
--top;
stack[++top] = v[i];
}
}
void Write() {
fout << top + 1 << '\n';
fout << setprecision(6) << fixed;
for (int i = 0; i <= top; ++i)
fout << stack[i].x << ' ' << stack[i].y << '\n';
}
int main() {
Read();
ConvexHull();
Write();
fin.close();
fout.close();
return 0;
}