Pagini recente » Cod sursa (job #3130087) | Cod sursa (job #1894698) | Cod sursa (job #1625431) | Cod sursa (job #2000557) | Cod sursa (job #872479)
Cod sursa(job #872479)
#include <iostream>
#include<fstream>
#include<iomanip>
#include <algorithm>
using namespace std;
#define MAXN 120050
int N;
struct Punct {
double x, y;
};
Punct P[MAXN];
Punct O;
int st[MAXN];
int varf;
inline double det(const Punct &A, const Punct &B, const Punct &C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline int cmp(const Punct &A, const Punct &B)
{
return det(P[1],A,B)>0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int poz;
f>>N;
f>>P[1].x>>P[1].y;
O=P[1];
poz=1;
for(int i = 2; i <= N; i++)
{
f>>P[i].x>>P[i].y;
if(P[i].x < O.x || (P[i].x == O.x && P[i].y < O.y))
{
O=P[i];
poz=i;
}
}
O=P[poz];
P[poz]=P[1];
P[1]=O;
sort(P+2, P + N+1, cmp);
st[1] = 1;
st[2] = 2;
varf = 2;
for(int i = 3; i<=N; i++)
{
while(varf >= 2 && det(P[st[varf - 1]], P[st[varf]],P[i]) <= 0)
varf--;
st[++varf] = i;
}
g<<fixed<<varf<<endl<<setprecision(9);
for(int i = 1; i<=varf; i++)
g<<P[st[i]].x<<' '<<P[st[i]].y<<endl;
g.close();
return 0;
}