Pagini recente » Cod sursa (job #2716006) | Cod sursa (job #2060426) | Cod sursa (job #94668) | Cod sursa (job #2065311) | Cod sursa (job #3208942)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
long double x,y;
};
Punct punctul_vietii;
int distanta(Punct a)
{
return (a.x-0)*(a.x-0)+(a.y-0)*(a.y-0);
}
int cadran(Punct a)
{
if(a.x>0 && a.y>=0)
return 1;
else if(a.x<=0 && a.y>0)
return 2;
else if(a.x<0 && a.y<=0)
return 3;
else if(a.x>=0 && a.y<0)
return 4;
}
long long cross_product(Punct &a, Punct &b)
{
return punctul_vietii.x*a.y+a.x*b.y+punctul_vietii.y*b.x-a.y*b.x-b.y*punctul_vietii.x-a.x*punctul_vietii.y;
}
long long det(Punct a, Punct b, Punct c)
{
return c.x*a.y+a.x*b.y+c.y*b.x-a.y*b.x-b.y*c.x-a.x*c.y;
}
bool cmp(Punct a,Punct b)
{
if(cadran(a)==cadran(b))
{
if(cross_product(a,b)==0)
return distanta(a)<distanta(b);
return cross_product(a,b)>0;
}
//return cadran(a)<cadran(b);
}
Punct v[120008];
vector<Punct>st;
double minst=1000008,minj=1000008;
int main()
{
int i,j,n,poz;
fin>>n;
for(i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(v[i].x<minst)
{
minst=v[i].x;
punctul_vietii=v[i];
poz=i;
}
else if(v[i].x==minst && v[i].y<minj)
{
minj=v[i].y;
punctul_vietii=v[i];
poz=i;
}
}
swap(v[1],v[poz]);
sort(v+2,v+n+1,cmp);
st.push_back(v[1]);
st.push_back(v[2]);
cout<<st.size()<<" ";
for(i=3;i<=n;i++)
{
while(st.size()>1 && det(st[st.size()-2],st[st.size()-1],v[i])<0)
{
st.pop_back();
}
st.push_back(v[i]);
}
// for(int i=1;i<=n;i++)
//{
// cout<<v[i].x<<" "<<v[i].y<<"\n";
// }
fout<<st.size()<<"\n";
// fout<<punctul_vietii.x<<" "<<punctul_vietii.y<<"\n";
for(i=0;i<st.size();i++)
{
fout<<fixed()<<setprecision(6)<<st[i].x<<" "<<st[i].y<<'\n';
}
return 0;
}