Pagini recente » Cod sursa (job #1575472) | Cod sursa (job #2393145) | Monitorul de evaluare | Cod sursa (job #120837) | Cod sursa (job #1501712)
#include <bits/stdc++.h>
using namespace std;
int n;
pair<double, double > P[120020];
///sortam dupa valoarea determinantului
/// luam primul punct fix si dupa daca det(a,b,c)<0 ->b<c
vector < int >v;
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 <const double ,const double > a, pair <const double,const double> b)
{
return det(P[1],a,b)>0;
}
};
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",&P[i].first,&P[i].second);
}
void infasuratoare()
{
int p=1,i;
for (i=2; i<=n; ++i)
if (P[i] < P[p])
p=i;
swap(P[1],P[p]);
sort(P+2,P+n+1,cmp());
v.push_back(1);
v.push_back(2);
for (i=3;i<=n;++i)
{
int siz=v.size();
while (siz>=2 && det (P[v[siz-2]],P[v[siz-1]],P[i])<0)
{
--siz;
v.pop_back();
}
v.push_back(i);
}
printf("%d\n",v.size ());
for (int i=0;i<v.size();++i)
printf("%lf %lf\n",P[v[i]].first,P[v[i]].second);
}
int main()
{
citire();
infasuratoare();
return 0;
}