Pagini recente » Cod sursa (job #2413063) | Cod sursa (job #1312749) | Cod sursa (job #1483296) | Cod sursa (job #42569) | Cod sursa (job #1414424)
#include<fstream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int nmax=120010;
const long long inf=100000000000;
int n;
struct point
{
double x,y,panta;
};
bool cmp(point i,point j) {return (i.panta<j.panta); }
point p[nmax];
vector<point> st;
double cp(point i,point j,point k)
{
return i.x*j.y+j.x*k.y+k.x*i.y-i.y*j.x-j.y*k.x-k.y*i.x;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>p[i].x>>p[i].y;
point first=p[1];int poz=1;
for (int i=2;i<=n;i++)
if (p[i].x<first.x || (p[i].x==first.x && p[i].y<first.y))
first=p[i],poz=i;
swap(p[1],p[poz]);
for (int i=2;i<=n;i++) p[i].panta=(p[i].x==p[1].x)?inf:(p[i].y-p[1].y)/(p[i].x-p[1].x);
sort(p+2,p+n+1,cmp);
st.push_back(p[1]);
st.push_back(p[2]);
for (int i=3;i<=n;i++) {
while (!st.empty() && cp(st[st.size()-1],st[st.size()-2],p[i])>=0)
st.pop_back();
st.push_back(p[i]);
}
cout<<st.size()<<"\n";
for (int i=0;i<st.size();i++) cout<<setprecision(12)<<fixed<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}