Pagini recente » Cod sursa (job #419365) | Cod sursa (job #467017) | Cod sursa (job #644) | Borderou de evaluare (job #135301) | Cod sursa (job #3223999)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
using point=pair<double,double>;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 12e4;
point v[MAXN + 1];
point *O = v;
bool cmp2(point &A, point &B) {
if (A.first == B.first)
return A.second < B.second;
return A.first < B.first;
}
bool 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);
}
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};
return crossProduct(AB, BC);
}
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 (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() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
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';
list<point> newpoli(poli.begin(), poli.end());
while (true) {
bool stop = true;
auto itr = newpoli.begin();
for (++itr; itr != newpoli.end(); itr++)
if (trigonometricOrder(*prev(itr), *itr, *next(itr))) {
itr = prev(newpoli.erase(itr));
stop = false;
}
if (stop)
break;
}
// 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);
poli = vector<point>(make_move_iterator(begin(newpoli)), make_move_iterator(end(newpoli)));
/*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;
}