Mai intai trebuie sa te autentifici.
Cod sursa(job #1136091)
Utilizator | Data | 8 martie 2014 19:04:00 | |
---|---|---|---|
Problema | Infasuratoare convexa | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.69 kb |
#include <cstdio>
#include <algorithm>
#include <cmath>
#define Nmax 120005
#define x first
#define y second
using namespace std;
int N,vf = 2;
pair<double,double> points[Nmax];
pair<double,double> S[Nmax];
/**
A.x A.y 1
B.x B.y 1 = A.x*B.y + B.x*C.y + C.x*A.y - A.y*B.x - B.y*C.x - C.y*A.x;
C.x C.y 1
**/
double cross(pair<int,int> A,pair<int,int> B,pair<int,int> C)
{
return A.x*B.y + B.x*C.y + C.x*A.y -
A.y*B.x - B.y*C.x - C.y*A.x;
}
double dist(pair<double,double > A, pair<double,double> B)
{
return sqrt((A.x - B.x)*(A.x - B.x) + (A.y - B.y)*(A.y - B.y));
}
class cmp{
public:
bool operator()(const pair<double,double> A,const pair<double,double> B) const
{
double x = cross(points[1],A,B);
if(x) return x < 0;
return dist(points[1],A) < dist(points[1],B);
}
};
void read()
{
scanf("%d",&N);
for(int i = 1; i <= N; ++i)
scanf("%lf%lf",&points[i].first,&points[i].second);
int pz = 1;
for(int i = 2; i <= N; ++i)
if(points[i] < points[pz])
pz = i;
swap(points[pz],points[1]);
sort(points+2,points+N+1,cmp());
}
void make_hull()
{
S[1] = points[1];
S[2] = points[2];
for(int i = 3; i <= N; ++i)
{
while(vf >= 2 && cross(S[vf-1],S[vf],points[i]) > 0)
--vf;
S[++vf] = points[i];
}
}
void print()
{
printf("%d\n",vf);
for(int i = vf; i >= 1; --i)
printf("%lf %lf\n",S[i].first,S[i].second);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
make_hull();
print();
return 0;
}