Pagini recente » Cod sursa (job #3345503) | Cod sursa (job #3308409) | Cod sursa (job #3349064) | Cod sursa (job #3346752) | Cod sursa (job #3321272)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long long ll;
typedef long double ld;
struct punct
{
ld x,y;
int id;
punct operator-(const punct &other)
{
return {x-other.x,y-other.y};
}
bool operator==(const punct &other)
{
return x==other.x&&y==other.y;
}
bool operator<(const punct &other)
{
return x<other.x||x==other.x&&y<other.y;
}
};
ld cross(punct a,punct b,punct c)
{
return (b.y-a.y)*(c.x-a.x)-(b.x-a.x)*(c.y-a.y);
}
punct zero;
ld dot(punct a,punct b,punct c)
{
return (b.x-a.x)*(c.x-a.x)+(b.y-a.y)*(c.y-a.y);
}
ld dist(punct a,punct b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(punct a,punct b)
{
return cross(zero,a,b)<0||cross(zero,a,b)==0&&dist(zero,a)<dist(zero,b);
}
vector <punct> convexhull(vector <punct>& pts)
{
if(pts.size()<=2)
return pts;
vector <punct> st;
for(int i=0;i<pts.size();i++)
if(pts[i]<pts[0])
swap(pts[i],pts[0]);
zero=pts[0];
sort(pts.begin()+1,pts.end(),cmp);
st.push_back(pts[0]);
st.push_back(pts[1]);
for(int i=2;i<pts.size();i++)
{
while(st.size()>=2&&cross(st[st.size()-2],st.back(),pts[i])>=0)
st.pop_back();
st.push_back(pts[i]);
}
return st;
}
int main()
{
int n;
fin>>n;
vector <punct> a(n);
for(int i=0;i<n;i++)
fin>>a[i].x>>a[i].y;
auto b=convexhull(a);
fout<<b.size()<<'\n';
for(auto p:b)
fout<<fixed<<setprecision(12)<<p.x<<' '<<p.y<<'\n';
return 0;
}