Pagini recente » Cod sursa (job #2588459) | Cod sursa (job #1493639) | Cod sursa (job #1373094) | Cod sursa (job #456967) | Cod sursa (job #2549190)
//ALEXANDRU MICLEA
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
using namespace std;
//#include <iostream>
#include <fstream>
ifstream cin("infasuratoare.in"); ofstream cout("infasuratoare.out");
//VARIABLES
struct POINT {
double x, y;
} point[120005];
vector <POINT> up;
vector <POINT> down;
int n;
//FUNCTIONS
bool cmp(POINT a, POINT b) {
if (a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
double det(POINT a, POINT b, POINT c) {
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
//MAIN
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> point[i].x >> point[i].y;
}
sort(point + 1, point + n + 1, cmp);
for (int i = 1; i <= n; i++) {
while (down.size() > 1 && det(down[down.size() - 2], down[down.size() - 1], point[i]) <= 0) {
down.pop_back();
}
down.push_back(point[i]);
}
for (int i = n; i >= 1; i--) {
while (up.size() > 1 && det(up[up.size() - 2], up[up.size() - 1], point[i]) <= 0) {
up.pop_back();
}
up.push_back(point[i]);
}
cout << down.size() + up.size() - 2 << '\n';
for (int i = 0; i < down.size() - 1; i++) {
cout << setprecision(12) << fixed << down[i].x << " " << down[i].y << '\n';
}
for (int i = 0; i < up.size() - 1; i++) {
cout << setprecision(12) << fixed << up[i].x << " " << up[i].y << '\n';
}
return 0;
}