Pagini recente » Cod sursa (job #1603873) | Cod sursa (job #1618947)
#include <iostream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<vector>
#define point pair<double,double>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,st[120002],top=0,start;
pair<double,double>p[120002];
double det( point x,point y,point z)
{
return (y.first-x.first)*(z.second-x.second)-(z.first-x.first)*(y.second-x.second);
}
double cmp(point x,point y)
{
return det(p[1],x,y)>0;
}
void citire()
{
f>>n;
start=1;
for(int i=1;i<=n;i++)
{
f>>p[i].first>>p[i].second;
if(p[i].second<p[start].second) start=i;
else if(p[i].second==p[start].second and p[i].first<p[start].first) start=i;
}
}
void rezolvare()
{
swap(p[1],p[start]);
sort(p+2,p+n+1,cmp);
for(int i=1;i<=n;i++)
{
while(top>=2 and det(p[i],p[st[top]],p[st[top-1]])>0 ) top--;
st[++top]=i;
}
}
void afisare()
{
g<<top<<"\n";
for(int i=1;i<=top;i++)
g<<fixed<<setprecision(6)<<p[st[i]].first<<" "<<p[st[i]].second<<"\n";
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}