Pagini recente » Cod sursa (job #754096) | Cod sursa (job #451912) | Cod sursa (job #1482994) | Cod sursa (job #81642) | Cod sursa (job #2553733)
#include<bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int st[120005];
struct punct
{
double x,y;
} a[120005],d;
int n,i,mn,nr;
double aa,bb;
bool egal(double x,double y)
{
if((x-y<0.000000000001&&x-y>=0)||(y-x<0.000000000001&&y-x>=0)) return 1;
return 0;
}
double det( punct A, punct B, punct C)
{
return (A.x - B.x) * (A.y - C.y) - (A.y - B.y) * (A.x - C.x);
}
double unghi(double x, double y)
{
double p1;
if(egal(aa+x,0)) p1=0;
else p1=(bb-y)/(aa+x);
return p1;
}
double compar(punct a,punct b)
{
double p1,p2;
if(egal(aa+a.x,0)) p1=(bb-a.y);
else p1=(bb-a.y)/(aa+a.x);
if(egal(aa+b.x,0)) p2=(bb-b.y);
else p2=(bb-b.y)/(aa+b.x);
if(p1==p2) return(bb-a.y<bb-b.y);
if(p1>=0&&p2>=0)
{
return p1>p2;
}
else if(p1>=0&&p2<0) return 1;
else if(p1<0&&p2>=0) return 0;
else
{
return p1>p2;
}
}
int main()
{
f>>n;
f>>a[1].x>>a[1].y;
mn=1;
for(i=2; i<=n; i++)
{
f>>a[i].x>>a[i].y;
if(a[i].x<a[mn].x)
{
mn=i;
}
else if(egal(a[i].x,a[mn].x)&&a[i].y<a[mn].y) mn=i;
}
if(a[mn].x>0) aa=a[mn].x;
else aa=-a[mn].x;
bb=a[mn].y;
d=a[mn];
sort(a+1,a+n+1,compar);
st[1]=1;
st[2]=2;
nr=2;
for(i=3; i<=n; i++)
{
while(nr>=2&&det(a[st[nr]],a[st[nr-1]],a[i])>0) nr--;
st[++nr]=i;
}
g<<nr+1<<'\n';
g<<fixed<<setprecision(6)<<d.x<<" "<<setprecision(6)<<d.y<<'\n';
for(i=1; i<=nr; i++) g<<setprecision(6)<<a[st[i]].x<<" "<<setprecision(6)<<a[st[i]].y<<'\n';
return 0;
}