Pagini recente » Cod sursa (job #1237866) | Cod sursa (job #491448) | Cod sursa (job #2240887) | Cod sursa (job #914503) | Cod sursa (job #2476106)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct{double x,y;}v[120001];
long long n,i,poz=1,s[120001],vf;
double arie(pct a,pct b,pct c)
{
return a.x*b.y-a.y*b.x+b.x*c.y-b.y*c.x+c.x*a.y-c.y*a.x;
}
long long dist(pct a,pct b)
{
return(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool mycmp(pct a,pct b)
{
if(arie(v[1],a,b)>0)return 1;
if(arie(v[1],a,b)==0)return dist(v[1],a)<dist(v[1],b);
if(arie(v[1],a,b)<0)return 0;
}
int main()
{
f>>n;
for(i=1;i<=n;i++)f>>v[i].x>>v[i].y;
poz=1;
for(i=2;i<=n;i++)if(v[i].y<v[poz].y||(v[i].y==v[poz].y&&v[i].x<v[poz].x))poz=i;
swap(v[poz],v[1]);
sort(v+2,v+n+1,mycmp);
cout<<endl;
s[1]=1;s[2]=2;vf=2;int nr=0;
for(i=3;i<=n;i++){
if(arie(v[s[vf-1]],v[s[vf]],v[i])>0)s[++vf]=i;
else if(arie(v[s[vf-1]],v[s[vf]],v[i])==0)s[vf]=i;
else{
while(vf>2&&arie(v[s[vf-1]],v[s[vf]],v[i])<0)vf--;
s[++vf]=i;
}
}
for(i=1;i<=vf;i++)v[i]=v[s[i]];
n=vf;
g<<n<<'\n';
for(i=1;i<=n;i++)g<<fixed<<setprecision(12)<<v[i].x<<" "<<v[i].y<<'\n';
return 0;
}