Pagini recente » Cod sursa (job #46581) | Cod sursa (job #537422) | Cod sursa (job #912452) | Cod sursa (job #575103) | Cod sursa (job #3223991)
#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 + 1];
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.first == B.first)
return A.second < B.second;
return A.first < B.first;
}
bool cmp3(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 crossProduct(point A, point B) {
return A.first * B.second > A.second * B.first;
}
double cmpcrossProduct(point A, point B) {
point AB = {O->first - A.first, O->second - A.second};
point BC = {B.first - O->first, B.second - O->second};
return crossProduct(AB, BC) > 0;
}
bool trigonometricOrder(point A, point B, point C) {
point AB = {B.first - A.first, B.second - A.second};
point BC = {C.first - B.first, C.second - B.second};
double cross = crossProduct(AB, BC);
return cross > 0;
}
ostream& operator<<(ostream &os, const point &a) {
os << a.first << ' ' << a.second;
return os;
}
int orientation(point p, point q, point r) {
double val = (q.second - p.second) * (r.first - q.first) - (q.first - p.first) * (r.second - q.second);
if (std::abs(val) < 1e-9) return 0; // Drepte coliniare
return (val > 0) ? 1 : 2; // 1 pentru sens trigonometric, 2 pentru sens invers trigonometric
}
// Funcție de comparație pentru a sorta punctele în funcție de unghiul lor față de un punct de referință
bool compare(point& p1, point& p2) {
// Considerăm un punct de referință arbitrar (0, 0)
int o = orientation(point(0, 0), p1, p2);
if (o == 0) {
// Dacă sunt coliniare, sortăm după distanță
return (p1.first * p1.first + p1.second * p1.second) < (p2.first * p2.first + p2.second * p2.second);
}
return (o == 1); // Sortăm în ordinea sensului trigonometric
}
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, cmpcrossProduct);
// for (int i = 0; i < n; i++)
// cout << v[i] << '\n';
vector<point> poli;
poli.push_back(*O);
v[n] = v[0];
for (int i = 1; i < n; i++) {
while (i < n && trigonometricOrder(*poli.rbegin(), v[i], v[i + 1]))
i++;
poli.push_back(v[i]);
//if (i == n - 1)
// poli.push_back(v[n - 1]);
}
//for (point elem: poli)
// cout << elem << '\n';
while (true) {
bool stop = true;
for (int i = 1; i < poli.size() - 1; i++)
if (trigonometricOrder(poli[i - 1], poli[i], poli[i + 1])) {
for (int j = i; j < poli.size() - 1; j++)
poli[j] = poli[j + 1];
poli.resize(poli.size() - 1);
i--;
stop = false;
}
if (stop)
break;
}
//sort(poli.begin(), poli.end(), compare);
reverse(poli.begin()+1, poli.end());
/*while (poli[0].second > poli[1].second) {
point aux = poli[0];
for (int i = 0; i < poli.size() - 1; i++)
poli[i] = poli[i + 1];
poli[poli.size() - 1] = aux;
}*/
fout << poli.size() << '\n';
for (point elem: poli)
fout << fixed << setprecision(14) << elem << '\n';
return 0;
}