Pagini recente » Cod sursa (job #431359) | Cod sursa (job #1522129) | Cod sursa (job #872579) | Istoria paginii runda/creaza_problema/clasament | Cod sursa (job #1506075)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define nmax 120001
using namespace std;
int n;
pair <double, double> v[nmax];
vector <int> p;
void citire()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d", &n);
for (int i=1;i<=n;++i)
scanf("%lf%lf",&v[i].first,&v[i].second);
}
double det(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}
struct cmp
{
bool operator()(pair<double, double> a, pair<double, double> b)
{
return det(v[1], a, b) > 0;
}
};
void infasuratoare()
{
int poz = 1;
for(int i = 2; i <= n; i++)
if(v[1] > v[poz])
poz = i;
swap(v[1], v[poz]);
sort(v+2,v+n+1, cmp());
for(int i = 1; i <= n; ++i) {
while(p.size() >= 2 && det(v[p[p.size()-2]],v[p[p.size()-1]],v[i]) < 0)
p.pop_back();
p.push_back(i);
}
printf("%d\n", p.size ());
for (int i=0; i<p.size(); ++i)
printf("%lf %lf\n", v[p[i]].first, v[p[i]].second);
}
int main()
{
citire();
infasuratoare();
return 0;
}