Pagini recente » Cod sursa (job #892972) | Cod sursa (job #2406102) | Cod sursa (job #786727) | Cod sursa (job #3252744) | Cod sursa (job #1126088)
#include <iomanip>
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define MAX 121000
pair<double, double> a[MAX];
int stiva[MAX], dr, stiva1[MAX], dr1;
inline bool cmp(pair<double, double> a, pair<double, double> b)
{
if(a.first==b.first)
return a.second>b.second;
return a.first<b.first;
}
bool dreapta(pair<double, double> a, pair<double, double> b, pair<double, double> c)
{
double x=b.first-a.first;
double y=b.second-a.second;
double x1=c.first-a.first;
double y1=c.second-a.second;
if(x==0)
return 0;
if(x1==0)
return 1;
return (double)y/x>(double)y1/x1;
}
int main()
{
int n, i;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>a[i].first>>a[i].second;
}
sort(a+1, a+n+1, cmp);
for(i=1;i<=n;i++)
{
while(dr>1 && dreapta(a[stiva[dr]], a[stiva[dr-1]], a[i]))
dr--;
stiva[++dr]=i;
}
for(i=1;i<=n;i++)
{
while(dr1>1 && !dreapta(a[stiva1[dr1]], a[stiva1[dr1-1]], a[i]))
{
dr1--;
}
stiva1[++dr1]=i;
}
fout<<dr1+dr-2<<"\n";
for(i=dr1-1;i>=1;i--)
{
fout<<fixed<<setprecision(6)<<a[stiva1[i]].first<<" "<<a[stiva1[i]].second<<"\n";
}
for(i=2;i<=dr;i++)
{
fout<<fixed<<setprecision(6)<<a[stiva[i]].first<<" "<<a[stiva[i]].second<<"\n";
}
}