Pagini recente » Cod sursa (job #1232106) | Cod sursa (job #161055) | Cod sursa (job #2083245) | Cod sursa (job #91324) | Cod sursa (job #2277873)
#include <fstream>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair <float,float> a[120001],s[120001];
int n;
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>a[i].first>>a[i].second;
sort(a+1,a+n+1);
int top=0;
s[++top]=a[1];
s[++top]=a[2];
//cout<<s[top].first<<" "<<s[top].second;
for(int i=3;i<=n;i++)
{
s[++top]=a[i];
while(top>=3&&s[top-2].first*s[top-1].second+s[top-1].first*s[top].second+s[top].first*s[top-2].second-s[top].first*s[top-1].second-s[top-2].first*s[top].second-s[top-1].first*s[top-2].second<0)
{
top--;
s[top]=s[top+1];
}
}
int k=top;
s[++top]=a[n-1];
for(int i=n-2;i>=1;i--)
{
s[++top]=a[i];
while(top>=k+2&&s[top-2].first*s[top-1].second+s[top-1].first*s[top].second+s[top].first*s[top-2].second-s[top].first*s[top-1].second-s[top-2].first*s[top].second-s[top-1].first*s[top-2].second<0)
{
top--;
s[top]=s[top+1];
}
}
top--;
fout<<top<<"\n";
for(int i=1;i<=top;i++)
fout<<s[i].first<<" "<<s[i].second<<"\n";
return 0;
}