Pagini recente » Cod sursa (job #2053433) | Cod sursa (job #657990) | Cod sursa (job #1657653) | Cod sursa (job #2493646) | Cod sursa (job #2327263)
#include <bits/stdc++.h>
#define Dim 120007
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int N,poz,ST[Dim],head;
typedef struct { double x,y; } Point;
double det(Point,Point);
Point 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 a,Point b)
{
return det(a,b,V[1])<0;
}
int main()
{
f>>N;
for(int i=1;i<=N;i++)
{
f>>V[i].x>>V[i].y;
if(i==1) poz=1;
else
if(V[i].y<V[poz].y) poz=i;
else
if(V[i].y==V[poz].y&&V[i].x<V[poz].x) poz=i;
}
swap(V[1],V[poz]);
sort(V+2,V+N+1,cmp);
ST[1]=1;
ST[2]=2;
head=2;
for(int i=3;i<=N;i++)
{
while(head>=2&&det(V[i],V[ST[head-1]],V[ST[head]])>0)
head--;
ST[++head]=i;
}
g<<head<<'\n';
g<<setprecision(9)<<fixed<<V[ST[1]].x<<" "<<V[ST[1]].y<<'\n';
for(int i=head;i>1;i--)
g<<setprecision(9)<<fixed<<V[ST[i]].x<<" "<<V[ST[i]].y<<'\n';
return 0;
}