Pagini recente » Cod sursa (job #2904355) | Cod sursa (job #365570) | Cod sursa (job #1652687) | Cod sursa (job #1188409) | Cod sursa (job #2757764)
#include <algorithm>
#include <complex>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
vector<complex<double>> v;
int N;
void read()
{
scanf("%d", &N);
double a, b;
for (int i = 0; i < N; ++i) {
scanf("%lf%lf", &a, &b);
v.emplace_back(a, b);
}
}
/**
| a.x a.y 1 | | a.x a.y 1|
| b.x b.y 1 | = | b.x-a.x b.y-a.y 0| = (b.x - a.x)*(c.y - a.y) - (c.x - a.x)*(b.y - a.y)
| c.x c.y 1 | | c.x-a.x c.y-a.y 0|
*/
double det(complex<double> a, complex<double> b, complex<double> c) {
return (b.real() - a.real()) * (c.imag() - a.imag()) -
(c.real() - a.real()) * (b.imag() - a.imag());
}
void calculateEnvelope(vector<complex<double>> v, vector<complex<double>> *envelope)
{
complex<double> leftmost = v.front();
complex<double> rightmost = v.back();
for (complex<double> p: v)
if (det(leftmost, rightmost, p) >= 0) {
while(envelope->size() >= 2 &&
det((*envelope)[(int)envelope->size() - 2],
(*envelope)[(int)envelope->size() - 1],
p) > 0)
envelope->pop_back();
envelope->emplace_back(p);
}
}
void convexHull()
{
vector<complex<double>> upper_envelope;
vector<complex<double>> lower_envelope;
sort(v.begin(),
v.end(),
[](const complex<double>& a, const complex<double>& b) {
if (a.real() == b.real())
return a.imag() < b.imag();
return a.real() < b.real();
});
calculateEnvelope(v, &upper_envelope);
reverse(v.begin(), v.end());
calculateEnvelope(v, &lower_envelope);
printf("%d\n", (int)upper_envelope.size() + (int)lower_envelope.size() - 2);
for (int i = (int)upper_envelope.size() - 1; i >= 0; --i)
printf("%lf %lf\n", upper_envelope[i].real(), upper_envelope[i].imag());
for (int i = (int)lower_envelope.size() - 2; i >= 1; --i)
printf("%lf %lf\n", lower_envelope[i].real(), lower_envelope[i].imag());
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
read();
convexHull();
return 0;
}