Pagini recente » Cod sursa (job #676125) | Cod sursa (job #3181809) | Cod sursa (job #244721) | Cod sursa (job #1361963) | Cod sursa (job #3268080)
#include <fstream>
#include<bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
#define int double
const signed N=1200005;
struct Point
{
int x,y;
}v[N],st[N];
int getDet(int X1,int Y1,int X2,int Y2,int X3,int Y3)
{
return X1*Y2+X2*Y3+X3*Y1-X3*Y2-X1*Y3-X2*Y1;
}
Point Origine;
bool cmp(Point a,Point b)
{
if (a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
bool cmp2(Point a,Point b)
{
return (a.y-Origine.y)*(b.x-Origine.x)>(b.y-Origine.y)*(a.x-Origine.x);
}
signed main()
{
signed n;
fin>>n;
for(signed i=1;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+n+1,cmp);
Origine.x=v[1].x;
Origine.y=v[1].y;
signed i;
for (i=1; i<=n; i++)
cout<<v[i].x<<" "<<v[i].y<<endl;
cout<<endl;
sort(v+2,v+n+1,cmp2);
for (i=1; i<=n; i++)
cout<<v[i].x<<" "<<v[i].y<<endl;
signed nr=0;
st[++nr].x=v[1].x;
st[nr].y=v[1].y;
st[++nr].x=v[2].x;
st[nr].y=v[2].y;
for(signed i=3;i<=n;i++)
{
while(nr>=2&&getDet(st[nr-1].x,st[nr-1].y,st[nr].x,st[nr].y,v[i].x,v[i].y)>0)
{
nr--;
}
st[++nr].x=v[i].x;
st[nr].y=v[i].y;
}fout<<nr<<"\n";
for(signed i=1;i<=nr;i++)
{
fout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<"\n";
}
return 0;
}