Pagini recente » Cod sursa (job #2543526) | Cod sursa (job #66770) | Cod sursa (job #2098628) | Cod sursa (job #692498) | Cod sursa (job #2376322)
#include <bits/stdc++.h>
#define Dim 120008
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,poz,head,S[Dim];
double a,b;
struct point
{
double x,y;
}V[Dim];
double det(point A,point B,point C)
{
return (A.x-C.x)*(B.y-C.y)-(A.y-C.y)*(B.x-C.x);
}
bool cmp(point X,point Y)
{
if(det(X,Y,V[1])<0) return 1;
else return 0;
}
int main()
{
f>>N;
for(int i=1;i<=N;i++)
{
f>>a>>b;
V[i]={a,b};
if(i==1) poz=1;
else
if(b<V[poz].y) poz=i;
else
if(b==V[poz].y&&a<V[poz].x) poz=i;
}
swap(V[1],V[poz]);
sort(V+2,V+N+1,cmp);
S[1]=1;
S[2]=2;
head=2;
for(int i=3;i<=N;i++)
{
while(head>=2&&det(V[i],V[S[head-1]],V[S[head]])>0) head--;
S[++head]=i;
}
g<<head<<'\n';
g<<fixed<<setprecision(12)<<V[S[1]].x<<" "<<V[S[1]].y<<'\n';
for(int i=head;i>1;i--)
g<<fixed<<setprecision(12)<<V[S[i]].x<<" "<<V[S[i]].y<<'\n';
return 0;
}