Pagini recente » Cod sursa (job #2029494) | Cod sursa (job #2085252) | Cod sursa (job #2085278) | Rating Voinea Vladimir (motionx77) | Cod sursa (job #2238414)
#include<bits/stdc++.h>
#define N 120010
#define POINT pair< double , double >
#define X first
#define Y second
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);
vector<POINT> P,ST;
double u,v,mic=0.00000001;
int main()
{
f>>n>>u>>v;
P.push_back(make_pair(u,v));
POINT Q=P[0];
int iq=0;
for(i=1; i<n; i++)
{
f>>u>>v;
P.push_back(make_pair(u,v));
if(P[i]<Q)
{
iq=i;
Q=P[i];
}
}
Q=P[iq];
P[iq]=P[0];
P[0]=Q;
sort(P.begin()+1,P.end(),comp);
ST.push_back(P[0]);
ST.push_back(P[1]);
vf=1;
for(i=2; i<n; i++)
{
while(!TRIG(ST[vf-1],ST[vf],P[i]))
{
ST.pop_back();
vf--;
}
vf++;
ST.push_back(P[i]);
}
g<<vf+1<<'\n';
for(auto it:ST)
g<<fixed<<setprecision(6)<<it.X<<' '<<it.Y<<'\n';
return 0;
}
int TRIG(POINT A,POINT B,POINT C)
{
return A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X>mic;
}
int comp(POINT A,POINT B)
{
return TRIG(P[0],A,B);
}