Pagini recente » Cod sursa (job #2172716) | Cod sursa (job #399547) | Cod sursa (job #860709) | Cod sursa (job #3138994) | Cod sursa (job #2375461)
#include<bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double,double> pct;
pct V[100001];
int k,st[100001];
pct start;
int n;
double crd(pct x, pct y, pct z)
{
return (x.first*y.second + z.first*x.second + y.first*z.second) - (z.first*y.second + z.second * x.first + y.first * x.second);
}
bool cmp(pct x,pct y)
{
return crd(V[1],x,y)>0;
}
int main()
{
f>>n;
for(int i=1;i<=n;++i)
{
f>>V[i].first>>V[i].second;
if(V[1]>V[i])
swap(V[i],V[1]);
}
sort(V+2,V+n+1,cmp);
st[++k]=1;
for(int i=2;i<=n;++i)
{
while(k>1 && crd(V[st[k-1]],V[st[k]],V[i])<=0)
k--;
st[++k]=i;
}
g<<k<<'\n';
for(int i=1;i<=k;++i)
g<<fixed<<setprecision(6)<<V[st[i]].first<<' '<<V[st[i]].second<<'\n';
}