Pagini recente » Cod sursa (job #3254032) | Cod sursa (job #1935936) | Cod sursa (job #2443042) | Cod sursa (job #2177484) | Cod sursa (job #2321253)
#include<bits/stdc++.h>
#define N 120010
#define POINT pair< double , double >
#define X first
#define Y second
#define DET(A,B,C) A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X
#define DIST(A,B) (A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y)
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,i,vf,comp(POINT A,POINT B),TRIG(POINT A,POINT B,POINT C);
POINT P[N],ST[N];
double u,v,mic=0.00000001;
void read(),solve(),convex_hull(),prints();
int main()
{
read();
solve();
return 0;
}
void read()
{
POINT Q;int iq;
f>>n;
f>>u>>v;P[0]=make_pair(u,v);
Q=P[0];iq=0;
for(i=1;i<n;i++)
{
f>>u>>v;P[i]=make_pair(u,v);
if(P[i]<Q){iq=i;Q=P[i];}
}
Q=P[iq];P[iq]=P[0];P[0]=Q;
}
void solve()
{
sort(P+1,P+n,comp);
convex_hull();
g<<vf+1<<'\n';
for(i=1;i<=vf;i++)
g<<fixed<<setprecision(10)<<ST[i].X<<' '<<ST[i].Y<<'\n';
i=0;
g<<fixed<<setprecision(10)<<ST[i].X<<' '<<ST[i].Y<<'\n';
}
int TRIG(POINT A,POINT B,POINT C)
{
double delta=DET(A,B,C),AB,AC;
if(delta>mic)return 1;
if(delta<-mic)return 0;
AB=DIST(A,B);AC=DIST(A,C);
if(AC-AB>mic)return 1;
return 0;
}
int comp(POINT A,POINT B)
{
return TRIG(P[0],A,B);
}
void convex_hull()
{
ST[0]=P[0];ST[1]=P[1];vf=1;
for(i=2;i<n;i++)
{
while(!TRIG(ST[vf-1],ST[vf],P[i]))vf--;
vf++;ST[vf]=P[i];
}
}