Pagini recente » Cod sursa (job #1045353) | Cod sursa (job #2653479) | Cod sursa (job #811353) | Cod sursa (job #1535167) | Cod sursa (job #1168155)
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 120000+5;
struct Point
{
double x,y;
Point()
{
x = y = 0;
}
};
double Cross_Product(const Point &A,const Point &B,const Point &C)
{
return (A.x - C.x) * (B.y - C.y) - (B.x - C.x) * (A.y - C.y);
}
void Read(),Solve(),Print();
int N;
Point P[NMAX];
int S[NMAX],top;
struct cmp
{
bool operator()(const Point &A, const Point &B)
{
return Cross_Product(P[1],A,B) > 0;
}
};
void Get_Leftmost_Downmost_Point()
{
int i,j = 1;
for(i = 2; i <= N; i++)
if(P[i].x == P[j].x && P[i].y < P[j].y) j = i;
else if(P[i].x < P[j].x) j = i;
swap(P[1],P[j]);
}
int main()
{
Read();
Solve();
Print();
return 0;
}
void Read()
{
int i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(i = 1; i <= N; i++)
scanf("%lf%lf",&P[i].x,&P[i].y);
}
void Solve()
{
int i;
Get_Leftmost_Downmost_Point();
sort(P+2,P+N+1,cmp());
for(i = 1; i <= N; i++)
{
while(top >= 2 && Cross_Product(P[S[top-1]],P[S[top]],P[i]) < 0) top--;
S[++top] = i;
}
}
void Print()
{
int i;
printf("%d\n",top);
for(i = 1; i <= top; i++)
printf("%lf %lf\n",P[S[i]].x,P[S[i]].y);
}