Pagini recente » Cod sursa (job #3215947) | Cod sursa (job #363499) | Cod sursa (job #356858) | Cod sursa (job #2288867) | Cod sursa (job #1420263)
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f3
int n;
double a,b;
struct point
{
double x,y,panta;
} p[120013];
vector < point > St;
struct comp
{
bool operator() (const point &a,const point &b)
{
return (a.panta<b.panta);
}
};
double det(point a,point b,point c)
{
return (a.x*b.y - a.y*b.x +
b.x*c.y - c.x*b.y +
c.x*a.y - a.x*c.y );
}
int main(void)
{
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
int poz=1;
for (int i=1;i<=n;++i)
{
cin>>a>>b;
p[i]={a,b};
if (a<p[poz].x || (a==p[poz].x && b<p[poz].y)) poz=i;
}
swap(p[poz],p[1]);
for (int i=2;i<=n;++i)
if (p[i].x==p[1].x) p[i].panta=inf;
else p[i].panta=(p[i].y-p[1].y)/(p[i].x-p[1].x);
sort(p+2,p+n+1,comp());
St.push_back(p[1]);
St.push_back(p[2]);
for (int i=3;i<=n;++i)
{
while (!St.empty() && det(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<<fixed<<setprecision(13)<<St[i].x<<" "<<St[i].y<<"\n";
return 0;
}