Pagini recente » Cod sursa (job #3183746) | Cod sursa (job #2073354) | Cod sursa (job #2281484) | Cod sursa (job #1525544) | Cod sursa (job #1883169)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define cout cerr
#define MAX 120001
using namespace std;
int n,sel,k=1,l_s;
vector <pair <double, double> > A;
int Q[MAX];
double x,y;
double determinant(pair <double, double> a, pair<double, double> b,pair <double, double> c)
{
double xa,ya,xb,yb,xc,yc;
xa=a.first;
ya=a.second;
xb=b.first;
yb=b.second;
xc=c.first;
yc=c.second;
return (xb-xa)*(yc-ya)-(xc-xa)*(yb-ya);
}
bool srt(pair <double, double> a, pair<double, double> b)
{
return (determinant(A[0],a,b) > 0);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
sel = 0;
for(int i=0; i<n; i++)
{
scanf("%lf %lf",&x,&y);
A.push_back(make_pair(x,y));
if(x<A[sel].first)
sel=i;
else if(x==A[sel].first)
if(y<A[sel].second)
sel=i;
}
if(sel!=0)
{
pair <double, double> aux;
aux = A[0];
A[0]=A[sel];
A[sel]=aux;
}
sort(A.begin()+1,A.end(),srt);
/*for(int i=0;i<n;i++)
cout<<A[i].first << " "<<A[i].second<<endl;
cout<<endl;*/
k=1;
Q[0]=0;
for(int i=1;i<n;i++)
{
while(k>1 && determinant(A[Q[k-2]],A[Q[k-1]],A[i])<0)
k--;
Q[k++]=i;
}
printf("%d\n",k);
for(int i=0;i<k;i++)
printf("%lf %lf\n",A[Q[i]].first,A[Q[i]].second);
return 0;
}