Pagini recente » Cod sursa (job #356770) | Cod sursa (job #1889170) | Cod sursa (job #1305349) | Cod sursa (job #1012685) | Cod sursa (job #3208933)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Punct
{
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;
}
int 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;
}
int 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[101];
vector<Punct>st;
long long minst=100000,minj=100000;
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<<st[i].x<<" "<<st[i].y<<'\n';
}
return 0;
}