Pagini recente » Monitorul de evaluare | Cod sursa (job #2192140) | Cod sursa (job #890739) | Cod sursa (job #1301271) | Cod sursa (job #3348816)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("infasuratoare.in");
ofstream out ("infasuratoare.out");
struct point{
long double x,y,tg;
};
long double delta(point a,point b,point c)
{
return b.x*c.y+c.x*a.y+a.x*b.y-b.x*a.y-c.x*b.y-a.x*c.y;
}
bool cmp(point a,point b)
{
if (a.tg==b.tg)
{
if (a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
return a.tg<b.tg;
}
vector <point> convexhull(vector <point> v)
{
point mn={1e18,1e18,67};
for (int i=0;i<v.size();i++)
{
if (mn.y>v[i].y || (mn.y==v[i].y && mn.x>v[i].x))
{
mn=v[i];
}
}
for (int i=0;i<v.size();i++)
{
if (mn.x==v[i].x && mn.y==v[i].y)
{
v.erase(v.begin()+i);
break;
}
}
for (int i=0;i<v.size();i++)
{
v[i].tg=atan2(v[i].y-mn.y,v[i].x-mn.x);
}
sort(v.begin(),v.end(),cmp);
vector <point> st;
st.push_back(mn);
for (int i=0;i<v.size();i++)
{
while (st.size()>1 && delta(st[st.size()-2],st[st.size()-1],v[i])<=0)
{
st.pop_back();
}
st.push_back(v[i]);
}
return st;
}
int main()
{
vector <point> v;
int n;
in>>n;
v.resize(n);
for (int i=0;i<n;i++)
{
in>>v[i].x>>v[i].y;
//out<<v[i].x<<" "<<v[i].y<<'\n';
}
out<<fixed<<setprecision(20);
v=convexhull(v);
out<<v.size()<<'\n';
for (int i=0;i<v.size();i++)
{
out<<v[i].x<<" "<<v[i].y<<'\n';
}
return 0;
}