Pagini recente » Cod sursa (job #852743) | Monitorul de evaluare | Istoria paginii utilizator/florea1985 | Cod sursa (job #970014) | Cod sursa (job #1776087)
#include <fstream>
#include <cmath>
#include <vector>
#define as a.size()
#define hs h.size()
using namespace std;
struct point{
double x,y,a;
} mp;
vector <point> h,a;
void lire()
{
ifstream f("infasuratoare.in");
int n; point p;
f >> n >> mp.x >> mp.y;
a.push_back(mp);
n--;
for ( ; n; n--)
{
f >> p.x >> p.y;
a.push_back(p);
if (p.x<mp.x || p.x==mp.x && p.y<mp.y) mp=p;
}
}
double det(point a, point b, point c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
bool comp(point a, point b)
{
if (a.a<b.a) return true; else return false;
}
void ca()
{
double x,y;
for (int i=0,q=as; i<as; i++)
{
x=a[i].x-mp.x;
y=a[i].y-mp.y;
if (x==0 && y==0) a[i].a=1.1; else
a[i].a=y*abs(y)/(x*x+y*y);
}
}
void hull()
{
h.push_back(a[0]);
h.push_back(a[1]);
h.push_back(a[2]);
if (det(h[0],h[1],h[2])<=0)
{
h[1]=h[2];
h.pop_back();
}
for (int i=3,q=as,w; i<q; i++)
{
h.push_back(a[i]);
w=hs;
while (w>2 && det(h[w-3],h[w-2],h[w-1])<=0)
{
h[w-2]=h[w-1];
h.pop_back();
w--;
}
}
}
void ecrire()
{
ofstream f("infasuratoare.out");
int q=hs;
f << '\n' << q << '\n';
for (int i=0; i<q; i++)
{
f << h[i].x << ' ' << h[i].y << '\n';
}
}
main()
{
lire();
ca();
sort(a.begin(),a.end(),comp);
hull();
ecrire();
}