Pagini recente » Cod sursa (job #458517) | Cod sursa (job #93932) | Cod sursa (job #520372) | Cod sursa (job #637244) | Cod sursa (job #2321256)
#include <bits/stdc++.h>
#define det(A,B,C) A.first*B.second+B.first*C.second+C.first*A.second-A.second*B.first-B.second*C.first-C.second*A.first
#define dist(A,B) (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second)
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
const double mic=0.00000001;
int n,i,j,iq,k;
double u,v;
pair<double,double> Q,P[120010],V[120010];
bool comp(pair<double,double> a,pair<double,double> b)
{
double val=det(P[0],a,b);
if(val> mic)return 1;
if(val<-mic)return 0;
double X=dist(P[0],a),Y=dist(P[0],b);
if(X-Y>mic)
return 0;
return 1;
}
int main()
{
f>>n;
f>>u>>v;
P[0]={u,v};
Q=P[0],iq=0;
for(i=1;i<n;i++)
{
f>>P[i].first>>P[i].second;
if(P[i]<Q)
Q=P[i],iq=i;
}
P[iq]=P[0];P[0]=Q;
sort(P+1,P+n,comp);
V[0]=P[0],V[1]=P[1],k=1;
for(i=2;i<n;i++)
{
while(k&&det(V[k-1],V[k],P[i])<-mic)
k--;
V[++k]=P[i];
}
g<<k+1<<'\n';
for(i=1;i<=k;i++)
g<<fixed<<setprecision(10)<<V[i].first<<' '<<V[i].second<<'\n';
g<<fixed<<setprecision(10)<<V[0].first<<' '<<V[0].second;
return 0;
}