Pagini recente » Cod sursa (job #2521780) | Cod sursa (job #1356775) | Cod sursa (job #1196976) | Cod sursa (job #151264) | Cod sursa (job #1146043)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define INF 21000000
#define DMAX 12000
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n,spoz,i,k;
struct punct{double x,y;}st[DMAX],v[DMAX],b[DMAX];
int cmp(punct a, punct b)
{
double m1,m2;
if(a.x==v[0].x) m1=INF;
else m1=(a.y-v[0].y)/(a.x-v[0].x);
if(b.x==v[0].x) m2=INF;
else m2=(b.y-v[0].y)/(b.x-v[0].x);
return m1<m2;
}
void merge_sort(int st, int dr)
{
if(st==dr)
return;
int mij=(st+dr)/2;
merge_sort(st,mij);
merge_sort(mij+1,dr);
int i=st,k=st,j=mij+1;
while(i<=mij && j<=dr)
if(cmp(v[i],v[j]))
b[k++]=v[i++];
else
b[k++]=v[j++];
if(i<=mij)
for(;i<=mij;++i)
b[k++]=v[i];
else
for(;j<=dr;++j)
b[k++]=v[j];
for(k=st;k<=dr;k++)
v[k]=b[k];
}
int calc(punct A, punct B, punct C){return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);}
int main()
{
fin>>n;
for(i=0;i<n;++i)
{
fin>>v[k].x;
fin>>v[k].y;
++k;
if(v[i].x<v[spoz].x || (v[i].x==v[spoz].x && v[i].y<v[spoz].y))
spoz=i;
}
swap(v[0],v[spoz]);
merge_sort(1,n-1);
st[1]=v[0];
st[2]=v[1];
int niv=2;
for(i=2;i<n;++i)
{
while(niv>=2 && calc(st[niv-1],st[niv],v[i])<=0)
--niv;
st[++niv]=v[i];
}
fout<<niv<<'\n';
for(i=1;i<=niv;++i)
fout<<setprecision(12)<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}