Pagini recente » Cod sursa (job #717457) | Cod sursa (job #3208948) | Cod sursa (job #636980) | Cod sursa (job #301204) | Cod sursa (job #3227199)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
const int NMAX = 120000;
const double INF = 1e10;
int n;
pair<double, double> pct[1 + NMAX];
vector<int> stiva;
double dist[1 + NMAX][1 + NMAX];
bool inInfasuratoare[1 + NMAX];
/*
x1 y1 1
x2 y2 1
x3 y3 1
> 0 stanga, sens trigonometric
< 0 dreapta
= 0 coliniare
x1 y1 = origine vector
x2 y2 = varf vector
x3 y3 = punctul de testat
*/
inline double det(double x1, double y1, double x2, double y2, double x3, double y3)
{
return x1 * y2 + x2 * y3 + x3 * y1 - x3 * y2 - x1 * y3 - x2 * y1;
}
inline double det(const pair<double, double>& pct1, const pair<double, double>& pct2, const pair<double, double>& pct3)
{
return pct1.first * pct2.second + pct2.first * pct3.second + pct3.first * pct1.second - pct3.first * pct2.second - pct1.first * pct3.second - pct2.first * pct1.second;
}
bool comp(const pair<double, double>& a, const pair<double, double>& b)
{
// a apare inaintea lui b daca e la dreapta de vectorul [pct(n) b]
return det(pct[n], b, a) <= 0;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in >> n;
for (int i = 1; i <= n; ++i)
in >> pct[i].first >> pct[i].second;
long long xMinim = INF;
long long yMinim = INF;
int indexMinim = -1;
for (int i = 1; i <= n; ++i)
{
if (pct[i].first < xMinim)
{
xMinim = pct[i].first;
yMinim = pct[i].second;
indexMinim = i;
}
else if (pct[i].first == xMinim)
{
if (pct[i].second < yMinim)
{
yMinim = pct[i].second;
indexMinim = i;
}
}
}
swap(pct[n], pct[indexMinim]);
sort(pct + 1, pct + 1 + n - 1, comp);
stiva.push_back(n);
for (int i = 1; i <= n; ++i)
{
while (stiva.size() >= 2 && det(pct[stiva[(int)stiva.size() - 2]], pct[stiva[(int)stiva.size() - 1]], pct[i]) <= 0)
stiva.pop_back();
stiva.push_back(i);
}
stiva.pop_back();
// Avem infasuratoarea convexa
out << stiva.size() << '\n';
for (int i = 0; i < stiva.size(); ++i)
{
out << setprecision(6) << fixed << pct[stiva[i]].first << ' ';
out << setprecision(6) << fixed << pct[stiva[i]].second <<'\n';
}
out << '\n';
/*
for (int i = 1; i <= n; ++i)
{
dist[i][i] = 0.0;
for (int j = i + 1; j <= n; ++j)
{
dist[i][j] = sqrt(1.0 * (pct[i].first - pct[j].first) * (pct[i].first - pct[j].first) + 1.0 * (pct[i].second - pct[j].second) * (pct[i].second - pct[j].second));
dist[j][i] = dist[i][j];
}
}
for (int i = 0; i < stiva.size(); ++i)
inInfasuratoare[stiva[i]] = true;
stiva.push_back(stiva[0]);
for (int r = 1; r <= n; ++r)
{
if (inInfasuratoare[r])
continue;
double distMinim = INF;
double raportMinim = INF;
int pozInStiva = -1;
for (int poz = 0; poz < (int)stiva.size() - 1; ++poz)
{
int i = stiva[poz];
int j = stiva[poz + 1];
if (dist[i][r] + dist[r][j] - dist[i][j] < distMinim)
{
distMinim = dist[i][r] + dist[r][j] - dist[i][j];
raportMinim = (dist[i][r] + dist[r][j]) / dist[i][j];
pozInStiva = poz;
}
else if (dist[i][r] + dist[r][j] - dist[i][j] == distMinim)
{
if ((dist[i][r] + dist[r][j]) / dist[i][j] < raportMinim)
{
raportMinim = (dist[i][r] + dist[r][j]) / dist[i][j];
pozInStiva = poz;
}
}
}
stiva.push_back(-1);
for (int i = (int)stiva.size() - 2; i >= pozInStiva + 1; --i)
stiva[i + 1] = stiva[i];
stiva[pozInStiva + 1] = r;
inInfasuratoare[r] = true;
}
xMinim = INF;
indexMinim = -1;
for (int i = 0; i < stiva.size(); ++i)
{
if (pct[stiva[i]].first < xMinim)
{
xMinim = pct[stiva[i]].first;
indexMinim = i;
}
}
for (int i = indexMinim; i < stiva.size(); ++i)
cout << pct[stiva[i]].first << ' ' << pct[stiva[i]].second << '\n';
for (int i = 0; i < indexMinim; ++i)
cout << pct[stiva[i]].first << ' ' << pct[stiva[i]].second << '\n';
cout << '\n';
*/
return 0;
}