Pagini recente » Cod sursa (job #2490619) | Cod sursa (job #1413839) | Cod sursa (job #837198) | Cod sursa (job #2133078) | Cod sursa (job #3213775)
#include <bits/stdc++.h>
#define N 120007
using namespace std;
ifstream fin("infasuratoare.in");ofstream fout("infasuratoare.out");
#define int double
vector<pair<int,int>>a;
int32_t n;
int32_t st[N];
bool viz[N];
int32_t top;
//inline bool Determinant( pair<int,int>x,pair<int,int>y,pair<int,int>z )
//{
// return (y.first*z.second -x.first*z.second
// -y.first*x.second -z.first*y.second
// +z.first*x.second +x.first*y.second)<=0;
//}
inline bool Determinant(pair<int,int> A, pair<int,int> B, pair<int,int> C)
{
return ( (A.second - B.second) * C.first + (B.first- A.first) * C.second
+ A.first * B.second - A.second* B.first )<=0;
}
int32_t main()
{
fin >> n;
for(int i=1;i<=n;i++)
{
pair<int,int>aux;
fin >> aux.second >> aux.first ;
a.push_back(aux);
}
sort(a.begin(),a.end());
for(int i=0;i<n;i++)
swap( a[i].first,a[i].second );
st[top]=0;
st[++top]=1;
// viz[0]=1;
viz[1]=1;
/// index 0
for(int32_t i=2;i<n;i++)
{
while( top>=1 and Determinant(a[st[top-1]],a[st[top]],a[i]) )
{
viz[ st[top] ]=0;
top--;
}
st[++top]=i;
viz[i]=1;
}
for(int32_t i=n-1;i>=0;i--)
if( !viz[i] )
{
while( top>=1 and Determinant(a[st[top-1]],a[st[top]],a[i]) )
top--;
st[++top]=i;
}
fout << top+1 <<"\n";
for(int i=0;i<=top;i++)
fout << setprecision(12) << fixed << a[i].first << " " << a[i].second << "\n";
return 0;
}