Pagini recente » Cod sursa (job #728455) | Cod sursa (job #420953) | Cod sursa (job #3175272) | Cod sursa (job #2551195) | Cod sursa (job #3222759)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
using point=pair<double,double>;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 12e4;
const double SHIFT= 1e9;
point v[MAXN];
point *O = v;
bool cmp(point &A, point &B) {
return (A.second - O->second)*(B.first - O->first) < (A.first - O->first)*(B.second - O->second);
}
bool cmp2(point &A, point &B) {
if (A.second == B.second)
return A.first < B.first;
return A.second < B.second;
}
point shift(point A) {
return {A.first + SHIFT, A.second + SHIFT};
}
double cmpcrossProduct(point A, point B) {
A = shift(A);
B = shift(B);
return A.first * B.second > A.second * B.first;
}
double crossProduct(point A, point B) {
return A.first * B.second > A.second * B.first;
}
bool trigonometricOrder(point A, point B, point C) {
// Calculam vectorii AB si BC
point AB = {B.first - A.first, B.second - A.second};
point BC = {C.first - B.first, C.second - B.second};
// Determinam produsul vectorial al acestor vectori
double cross = crossProduct(AB, BC);
// Verificam semnul produsului vectorial pentru a stabili ordinea trigonometrica
return cross > 0;
}
int main() {
int n;
fin >> n;
for (int i = 0; i < n; i++)
fin >> v[i].first >> v[i].second;
sort(v, v + n, cmp2);
sort(v + 1, v + n, cmp);
vector<point> poli;
poli.push_back(*O);
poli.push_back(v[1]);
for (int i = 2; i < n - 1; i++) {
while (i < n - 1 && !trigonometricOrder(*poli.rbegin(), v[i], v[i + 1]))
i++;
poli.push_back(v[i]);
if (i == n - 2)
poli.push_back(v[n - 1]);
}
//sort(poli.begin(), poli.end(), crossProduct);
fout << poli.size() << '\n';
for (point elem: poli)
fout << fixed << setprecision(14) << elem.first << ' ' << elem.second << '\n';
return 0;
}