Pagini recente » Cod sursa (job #2172119) | Cod sursa (job #3268288) | Cod sursa (job #3178338) | Cod sursa (job #780567) | Cod sursa (job #2556583)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
struct point {
double x, y;
} puncte[120004];
bool compare(point x, point y) {
return x.x < y.x;
}
void citire() {
f >> n;
for (int i = 0; i < n; ++i) {
f >> puncte[i].x >> puncte[i].y;
}
}
void afis(point a) {
g<< a.x << " " << a.y << '\n';
}
bool sens_trigo(point A, point B, point C) {
double det = (A.x - C.x) * (B.y - C.y) - (A.y - C.y) * (B.x - C.x);
return det > 0;
}
void rezolvare() {
vector<point> rez1, rez2;
int nr1 = 2, nr2 = 2;
rez1.push_back(puncte[0]);
rez1.push_back(puncte[1]);
for (int i = 2; i < n; i++) {
while (nr1 > 1 && !sens_trigo(rez1[nr1 - 2], rez1[nr1 - 1], puncte[i])) {
nr1--;
rez1.pop_back();
}
rez1.push_back(puncte[i]);
nr1++;
}
rez2.push_back(puncte[n - 1]);
rez2.push_back(puncte[n - 2]);
for (int i = n - 3; i >= 0; i--) {
while (nr2 > 1 && !sens_trigo(rez2[nr2 - 2], rez2[nr2 - 1], puncte[i])) {
nr2--;
rez2.pop_back();
}
rez2.push_back(puncte[i]);
nr2++;
}
rez1.pop_back();
rez2.pop_back();
g << nr1 + nr2 - 2 << endl;
g<<setprecision(13)<<fixed;
for (int i = 0; i < nr1 - 1; i++) {
afis(rez1[i]);
}
for (int i = 0; i < nr2 - 1; i++) {
afis(rez2[i]);
}
}
int main() {
citire();
sort(puncte, puncte + n, compare);
rezolvare();
return 0;
}