Pagini recente » Cod sursa (job #1049588) | Cod sursa (job #1630780) | Cod sursa (job #1429503) | Cod sursa (job #756651) | Cod sursa (job #821329)
Cod sursa(job #821329)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#define NM 120010
#define INF 99999999999.0
#define EPS 1e-12
#define x first
#define y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
double Equal (double A, double B)
{
return fabs(A-B)<EPS;
}
typedef pair<double, double> PI;
PI G;
double Tang (PI P)
{
if (Equal(P.x,G.x)) return INF;
return 1.0*(P.y-G.y)/(P.x-G.x);
}
bool CMP (PI A, PI B)
{
return Tang(A)<Tang(B);
}
int N;
int i,j;
int P;
PI V[NM];
PI S[NM];
int K;
int Sign (PI P1, PI P2, PI P3)
{
double S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
if (Equal(S,0.0)) return 0;
return (S<0?-1:1);
}
int main ()
{
f >> N;
V[0].x=V[0].y=INF;
for (i=1; i<=N; i++)
{
f >> V[i].x >> V[i].y;
if (V[i].x<V[P].x || (Equal(V[i].x,V[P].x) && V[i].y<V[P].y))
P=i;
}
swap(V[1],V[P]);
G=V[1];
sort(V+2,V+N+1,CMP);
S[K=1]=V[1];
for (i=2; i<=N; i++)
{
while (K>1 && Sign(S[K-1],S[K],V[i])<0) --K;
S[++K]=V[i];
}
g << K << '\n';
for (i=2; i<=K; i++)
g << fixed << setprecision(12) << S[i].x << ' ' << S[i].y << '\n';
g << fixed << setprecision(12) << S[1].x << ' ' << S[1].y << '\n';
f.close();
g.close();
return 0;
}