Pagini recente » Cod sursa (job #2883404) | Cod sursa (job #1081617) | Cod sursa (job #2647828) | Cod sursa (job #3041) | Cod sursa (job #2503364)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
#include <cmath>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct punct {
double x, y;
void print_punct() {
out << x << ' ' << y << '\n';
}
bool operator==(const punct& B) {
if (abs(x - B.x) < 0.000001 && abs(y - B.y) < 0.000001)
return true;
return false;
}
};
bool cmp(punct& A, punct& B) {
if (A.x < B.x)
return true;
if (A.x > B.x)
return false;
if (A.y < B.y)
return true;
return false;
}
bool viraj(vector <punct>& stiva) {
int n = stiva.size();
double x1 = stiva[n - 3].x, y1 = stiva[n - 3].y;
double x2 = stiva[n - 2].x, y2 = stiva[n - 2].y;
double x3 = stiva[n - 1].x, y3 = stiva[n - 1].y;
double det = x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
if (det > 0)
return true;
return false;
}
int main() {
int n;
in >> n;
vector <punct> A(n);
for (int i = 0; i < n; i++) {
in >> A[i].x >> A[i].y;
}
sort(A.begin(), A.end(), cmp);
punct st = A[0], dr = A[n - 1];
vector <punct> stiva;
stiva.push_back(A[0]);
stiva.push_back(A[1]);
for (int i = 2; i < n; i++) {
stiva.push_back(A[i]);
while (stiva.size() > 2 && !viraj(stiva)) {
stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
stiva.pop_back();
}
}
vector <punct> sol = stiva;
stiva.clear();
stiva.push_back(A[n - 1]);
stiva.push_back(A[n - 2]);
for (int i = n - 3; i >= 0; i--) {
stiva.push_back(A[i]);
while (stiva.size() > 2 && !viraj(stiva)) {
stiva[stiva.size() - 2] = stiva[stiva.size() - 1];
stiva.pop_back();
}
}
for (int i = 1; i < stiva.size() - 1; i++)
sol.push_back(stiva[i]);
out << fixed << setprecision(12);
out << sol.size() << '\n';
for (auto &&el: sol) {
el.print_punct();
}
return 0;
}