Pagini recente » Cod sursa (job #1968397) | Cod sursa (job #1844997)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define ll long double
using namespace std;
ifstream f("infasuratoareconvexa.in");
ofstream g("infasuratoareconvexa.out");
struct point {
ll x, y;
};
int n,k;
vector<point> v(120005);
vector<point> s(120005);
void citire()
{
f>>n;
int i;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
}
ll det(const point& A, const point& B, const point& C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
bool cmp1(point a, point b)
{
return (a.x<b.x) or ((a.x==b.x) and (a.y<b.y));
}
bool cmp2(const point& p1, const point& p2)
{
return det(v[1],p1,p2)<0;
}
void sortare()
{
int pos=1,i;
for(i=2;i<=n;i++)
if(cmp1(v[i],v[pos]))
pos=i;
swap(v[1],v[pos]);
sort(v.begin()+2,v.begin()+n+1,cmp2);
}
void solve()
{
int i;
sortare();
k=2;
s[1]=v[1];
s[2]=v[2];
for(i=3;i<=n;i++)
{
while(k>=2 and det(s[k-1],s[k],v[i])>0)
k--;
s[++k]=v[i];
}
}
void afisare()
{
g<<k<<'\n';
int i;
for(i=k;i>=1;i--)
{
g<<fixed<<setprecision(6)<<s[i].x<<' ';
g<<fixed<<setprecision(6)<<s[i].y<<'\n';
}
}
int main()
{
citire();
solve();
afisare();
return 0;
}