Pagini recente » Cod sursa (job #310681) | Cod sursa (job #2905787) | Cod sursa (job #2405243) | Cod sursa (job #2441082) | Cod sursa (job #2547240)
#include <bits/stdc++.h>
#define punct pair<double,double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const int N = 120010;
double x,y;
int n,m;
punct p[N];
bool crit(punct,punct);
double det(punct,punct,punct);
int main()
{ f>>n;
for(int i=0;i<=n;i++)
{
f>>x>>y;
p[i]=make_pair(x,y);
if(p[i]<p[0]) swap(p[i],p[0]);
}
sort(p+1,p+n,crit);
m=1;
for(int i=2;i<n;i++)
{
while(det(p[m-1],p[m],p[i])<0)
m--;
p[++m]=p[i];
}
g<<m+1<<'\n';
for(int i=0;i<=m;i++)
g<<fixed<<setprecision(10)<<p[i].first<<' '<<p[i].second<<'\n';
return 0;
}
double det(punct A,punct B,punct C)
{
double a1,b1;tie(a1,b1)=A;
double a2,b2;tie(a2,b2)=B;
double a3,b3;tie(a3,b3)=C;
return a1*b2+a2*b3+a3*b1-(a1*b3+a3*b2+a2*b1);
}
bool crit(punct A,punct B)
{
return det(p[0],A,B)>=0;
}