Pagini recente » Cod sursa (job #2536998) | Cod sursa (job #2302958) | Cod sursa (job #127951) | Cod sursa (job #3266616) | Cod sursa (job #3346218)
#include <bits/stdc++.h>
#define NMAX 120009
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N,M;
struct punct
{
double x,y;
} v[NMAX],hull[2*NMAX];
void citire()
{
fin>>N;
for(int i=0; i<N; i++)
{
fin>>v[i].x>>v[i].y;
}
}
bool cmp(punct A, punct B)
{
if(A.x!=B.x)
{
return A.x<B.x;
}
else
{
return A.y<B.y;
}
}
double arie(punct A, punct B, punct C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
}
int main()
{
citire();
sort(v,v+N,cmp);
for(int i=0; i<N; i++)
{
while(M>=2 && arie(hull[M-2],hull[M-1],v[i])<=0)
{
M--;
}
hull[M++]=v[i];
}
for(int i=N-1,j=M+1; i>0; i--)
{
while(M>=j && arie(hull[M-2],hull[M-1],v[i-1])<=0)
{
M--;
}
hull[M++]=v[i-1];
}
M--;
fout<< M << "\n";
for(int i=0; i<M; i++)
{
fout<< fixed << setprecision(6) << hull[i].x << " " << hull[i].y << "\n";
}
return 0;
}