Pagini recente » Cod sursa (job #1967431) | Cod sursa (job #1298062) | Cod sursa (job #1800384) | Cod sursa (job #1970323) | Cod sursa (job #1300417)
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define nmax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct POINT {
double x, y;
} P[nmax], S[nmax];
int n, sSize;
int st[nmax];
bool VIZ[nmax];
void readData() {
int i;
fin >> n;
for (i = 1; i <= n; i++)
fin >> P[i].x >> P[i].y;
}
bool cmp(POINT a, POINT b) {
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double det(POINT A, POINT B, POINT O) {
return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}
void solve() {
int i;
sort(P+1, P+n+1, cmp);
st[1] = 1;
st[2] = 2;
VIZ[st[1]] = VIZ[st[2]] = true;
sSize = 2;
for (i = 3; i <= n; i++) {
while (sSize > 1 && det(P[st[sSize-1]], P[st[sSize]], P[i]) < 0.000000000001) {
VIZ[st[sSize]] = false;
sSize--;
}
sSize++;
st[sSize] = i;
VIZ[st[sSize]] = true;
}
for (i = n-1; i > 0; i--) {
if (VIZ[i])
continue;
if (det(P[st[sSize-1]], P[st[sSize]], P[i]) < 0)
sSize--;
sSize++;
st[sSize] = i;
}
}
void writeData() {
int i;
fout << sSize << "\n";
fout << fixed;
for (i = 1; i <= sSize; i++)
fout << setprecision(6) << P[st[i]].x << " " << P[st[i]].y << "\n";
}
int main() {
readData();
solve();
writeData();
fin.close();
fout.close();
return 0;
}