Pagini recente » Diferente pentru preoni-2007/runda-finala/poze/wii-play intre reviziile 3 si 4 | Cod sursa (job #1983949)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point {
double x, y;
bool operator< (const point& other) const {
if (x != other.x)
return x < other.x;
return y < other.y;
}
};
const int NMAX = 120002;
int n;
point v[NMAX];
point stk[NMAX];
int stackTop;
inline void read() {
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> v[i].x >> v[i].y;
}
}
inline double crossProduct(const point& a, const point& b, const point& c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
inline bool cmp(const point& a, const point& b) {
return crossProduct(v[1], a, b) < 0;
}
inline void sortPoints() {
int pos = 1;
for (int i = 2; i <= n; ++i)
if (v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v + 2, v + n + 1, cmp);
}
inline void convexHull() {
sortPoints();
stk[1] = v[1];
stk[2] = v[2];
stackTop = 2;
for (int i = 3; i <= n; ++i) {
while (stackTop >= 2 && crossProduct(stk[stackTop - 1], stk[stackTop], v[i]) > 0)
--stackTop;
stk[++stackTop] = v[i];
}
}
inline void write() {
fout << stackTop << '\n';
for (int i = stackTop; i; --i)
fout << fixed << setprecision(9) << stk[i].x << ' ' << stk[i].y << '\n';
}
int main()
{
read();
convexHull();
write();
fin.close();
fout.close();
return 0;
}