Pagini recente » Cod sursa (job #2044491) | Cod sursa (job #1350561) | Cod sursa (job #1440808) | Cod sursa (job #2770725) | Cod sursa (job #3219295)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct
{
double long x,y;
}v[120005];
bool cmp(punct a,punct b)
{
if(a.x<b.x)
return true;
else
if(a.x==b.x)
if(a.y<b.y)
return true;
}
vector <punct> st;
punct rasp[120005];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i].x>>v[i].y;
long double S=0;
sort(v+1,v+n+1, cmp);
st.push_back(v[1]);
int k=1;
for(int i=2;i<=n;i++)
{
if(k>=3)
{
long double s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
while(s<0 && k>2)
{
st.pop_back();
s=s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
k--;
}
}
st.push_back(v[i]);
k++;
}
for(int i=1;i<=k;i++)
rasp[i]=st[i];
st.clear();
int ck=k;
k=1;
st.push_back(v[n]);
for(int i=n-1;i>=1;i--)
{
if(k>=3)
{
long double s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
while(s>0 && k>2)
{
st.pop_back();
s=s=st[k-2].x*(st[k-1].y-v[i].y)+st[k-1].x*(v[i].y-st[k-2].y)+v[i].x*(st[i-2].y-st[i-1].y);
k--;
}
}
st.push_back(v[i]);
k++;
}
cout<<ck+k-1<<'\n';
for(int i=1;i<ck;i++)
cout<<rasp[i].x<<" "<<rasp[i].y<<'\n';
for(int i=2;i<k;i++)
cout<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}