Pagini recente » Cod sursa (job #2731817) | Cod sursa (job #3186602) | Cod sursa (job #3125961) | Cod sursa (job #203582) | Cod sursa (job #2881528)
#include <bits/stdc++.h>
using namespace std;
double arie (pair<double, double> A, pair<double, double> B, pair<double, double> C)
{
return A.first*B.second + B.first*C.second + C.first*A.second -
C.first*B.second - A.first*C.second - B.first*A.second;
}
bool cmp (pair<double, double> a, pair<double, double> b)
{
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
pair<double, double> coord[120000];
int main()
{
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n, i;
fin >> n;
pair<double, double> pmin, pmax;
pmin.second = 1000000000;
pmin.first = 1000000000;
pmax.second = -1000000000;
pmax.first = -1000000000;
for (i = 0; i < n; i++)
{
fin >> coord[i].first >> coord[i].second;
if (cmp(coord[i], pmin))
{
pmin = coord[i];
}
if (!cmp(coord[i], pmax))
{
pmax = coord[i];
}
}
vector<pair<double, double> > dreapta;
vector<pair<double, double> > stanga;
for (i = 0; i < n; i++)
{
if (coord[i] != pmax && coord[i] != pmin)
{
double aria = arie(pmin, pmax, coord[i]);
if (aria < 0)
dreapta.push_back(make_pair(coord[i].first, coord[i].second));
else stanga.push_back(make_pair(coord[i].first, coord[i].second));
}
}
sort(dreapta.begin(), dreapta.end(), cmp);
sort(stanga.begin(), stanga.end(), cmp);
int vf = 0;
pair<double, double> stiv[120000];
stiv[vf++] = pmin;
stiv[vf++] = dreapta[0];
for (i = 1; i < dreapta.size(); i++)
{
if ( arie(stiv[vf-2], stiv[vf-1], dreapta[i]) > 0 )
stiv[vf++] = dreapta[i];
else
{
while (arie(stiv[vf-2], stiv[vf-1], dreapta[i]) < 0)
{
vf--;
}
stiv[vf++] = dreapta[i];
}
}
if (arie(stiv[vf-2], stiv[vf-1], pmax) < 0)
vf--;
stiv[vf++] = pmax;
stiv[vf++] = stanga[stanga.size() - 1];
for (i = stanga.size() -2; i >= 0; i--)
{
if ( arie(stiv[vf-2], stiv[vf-1], stanga[i]) > 0 )
stiv[vf++] = stanga[i];
else
{
while (arie(stiv[vf-2], stiv[vf-1], stanga[i]) < 0)
{
vf--;
}
stiv[vf++] = stanga[i];
}
}
if (arie(stiv[vf-2], stiv[vf-1], pmin) < 0)
vf--;
int puncte = vf;
fout << puncte << '\n';
fout << setprecision(6) << fixed;
for (i = 0; i < puncte; i++)
{
if (i == puncte - 1)
fout << stiv[i].first << " " << stiv[i].second;
else fout << stiv[i].first << " " << stiv[i].second << '\n';
}
fin.close();
fout.close();
return 0;
}