Pagini recente » Cod sursa (job #2267112) | Cod sursa (job #1821069) | Cod sursa (job #1346229) | Cod sursa (job #2233416) | Cod sursa (job #2060519)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define MAXN 120007
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N, nn, s[MAXN], cont;
bool ok[MAXN];
struct punct{
double x, y;
};
punct v[MAXN];
inline bool cum(punct A, punct B) {
if (A.y == B.y)
return A.x < B.x;
return A.y < B.y;
}
inline void Read() {
fin >> N;
for (int i = 1; i <= N; i++) {
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + N + 1, cum);
}
///ok[i] = 1 - elementul i apare in stiva
inline double semn(punct p1, punct p2, punct p3) {
double vall = (p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - (p3.x * p2.y + p1.x * p3.y + p2.x * p1.y));
return vall;
}
inline void Solve() {
s[1] = 1; s[2] = 2; nn = 2; int ii = 2;
double val;
cont = 1;///parcurg elementele
ok[2] = 1;
while (!ok[1]) {
while (ok[ii]) {
if (ii == N)
cont *= -1;
ii += cont;
}
do {
val = 0;
if (nn < 2) {
s[++nn] = ii;
break;
}
else {
val = semn(v[s[nn - 1]], v[s[nn]], v[ii]);
if (val < 0)
s[++nn] = ii,
ok[ii] = 1;
else if (val > 0) {
ok[s[nn]] = 0;
nn--;
}
else
ii++;
}
} while (val > 0);
}
}
inline void Write() {
fout << nn - 1 << "\n";
for (int i = nn; i > 1; i--)
fout << fixed << setprecision(6) << v[s[i]].x << " " << v[s[i]].y << "\n";
}
int main () {
Read();
Solve();
Write();
fin.close(); fout.close(); return 0;
}