Pagini recente » Cod sursa (job #2661501) | Cod sursa (job #905586) | Cod sursa (job #3002963) | Cod sursa (job #2243287) | Cod sursa (job #870287)
Cod sursa(job #870287)
#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;
double crossProduct(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);
}
//conditia corecta (cand sunt ordonate)
inline int cmp(const Punct &A, const Punct &B)
{
return (A.y < B.y || (A.y == B.y && A.x < B.x));
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int poz;
f>>N;
f>>setprecision(12)>>fixed;
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].y < O.y || (P[i].y == O.y && P[i].x < O.x))
{
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 >= 1 && crossProduct(P[st[varf - 1]], P[i], P[st[varf]]) > 0)
varf--;
st[++varf] = i;
}
g<<varf<<endl;
g<<setprecision(12)<<fixed;
for(int i = 1; i <= varf; i++)
g<<P[st[i]].x<<' '<<P[st[i]].y<<endl;
g.close();
return 0;
}