Pagini recente » Borderou de evaluare (job #1652912) | Cod sursa (job #2715808) | Cod sursa (job #2611783) | Cod sursa (job #2096611) | Cod sursa (job #980690)
Cod sursa(job #980690)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N = 120010;
const int oo = (1 << 20);
int n, top = 2;
typedef pair <double, double> punct;
punct p[N], st[N], p0;
inline double Sign(punct p1, punct p2, punct p3)
{
return (p2.x-p1.x)*(p3.y-p1.y) - (p3.x-p1.x)*(p2.y-p1.y);
}
inline bool cmp(const punct& a, const punct& b)
{
return Sign(p0, a, b) < 0;
}
int main()
{
fin>>n;
for(int i=1; i<=n; i++)
fin>>p[i].x>>p[i].y;
int poz; double ord = oo, abs = oo;
for(int i=1; i<=n; i++)
if(p[i].y < ord) ord = p[i].y, poz = i; else
if(p[i].y == ord && p[i].x < abs) abs = p[i].x, poz = i;
p0 = p[poz];
sort(p+1, p+n+1, cmp);
st[1] = p[1]; st[2] = p[2];
for(int i=3; i<=n; i++)
{
while(top > 1 && Sign(st[top-1], st[top], p[i]) > 0)
top--;
st[++top] = p[i];
}
fout<<top<<'\n';;
fout<<fixed<<setprecision(6);
for(int i=1; i<=top; i++)
fout<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}