Pagini recente » Cod sursa (job #2352494) | Cod sursa (job #2171320) | Cod sursa (job #2516769) | Cod sursa (job #98722) | Cod sursa (job #2321244)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoarea.in");
ofstream g("infasuratoarea.out");
const double mic=1e-7;
int n,i,j,iq,k;
double u,v;
pair<double,double> Q,P[120010],V[120010];
double dist(pair<double,double> a,pair<double,double> b)
{
return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
double det(pair<double,double> a,pair<double,double> b,pair<double,double> c)
{
return (a.first*b.second+c.first*a.second+b.first*c.second-
(c.first*b.second+a.first*c.second+b.first*a.second));
}
bool comp(pair<int,int> a,pair<int,int> 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)
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=0;i<=k;i++)
g<<V[i].first<<' '<<V[i].second<<'\n';
return 0;
}