Pagini recente » Cod sursa (job #1581685) | Cod sursa (job #1824698) | Cod sursa (job #1290440) | Cod sursa (job #1336648) | Cod sursa (job #582543)
Cod sursa(job #582543)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 120010
fstream fin ("infasuratoare.in", ios::in);
int n, pi = 1;
pair <double, double> pt[MAXN];
vector <int> ind, sol;
typedef vector <int>::iterator iter;
bool cmp (int a, int b)
{
return (double)(pt[a].first - pt[pi].first) * (pt[b].second - pt[pi].second) < (double)(pt[b].first - pt[pi].first) * (pt[a].second - pt[pi].second);
}
bool sgn (int a, int b, int c)
{
return ((long double)pt[a].first * pt[b].second + pt[b].first * pt[c].second + pt[c].first * pt[a].second - pt[a].second * pt[b].first - pt[b].second * pt[c].first - pt[c].second * pt[a].first) > 0;
}
int main ()
{
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> pt[i].first >> pt[i].second;
if ((pt[pi].first == pt[i].first) ? (pt[pi].second > pt[i].second) : (pt[pi].first > pt[i].first)) {
pi = i;
}
}
for (int i = 1; i <= n; ++i) {
if (i != pi) {
ind.push_back (i);
}
}
sort (ind.begin (), ind.end (), cmp);
sol.push_back (pi);
for (iter it = ind.begin (); it != ind.end (); ++it) {
while (sol.size () >= 2 && sgn (*(sol.end () - 2), *(sol.end () - 1), *it)) {
sol.pop_back ();
}
sol.push_back (*it);
}
freopen ("infasuratoare.out", "wt", stdout);
sol.push_back (pi);
reverse (sol.begin (), sol.end ());
printf ("%d\n", sol.size () - 1);
for (iter it = sol.begin (); it != sol.end () - 1; ++it) {
printf ("%lf %lf\n", pt[*it].first, pt[*it].second);
}
fin.close ();
return 0;
}