Pagini recente » Cod sursa (job #2476189) | Cod sursa (job #152953) | Cod sursa (job #270447) | Cod sursa (job #2988076) | Cod sursa (job #1776103)
#include <fstream>
#include <algorithm>
#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 qs(int le,int ri)
{
int i=le, j=ri; point p=a[(i+j)/2];
while (i<j)
{
while (a[i].a<p.a) i++;
while (a[j].a>p.a) j--;
if (i<=j)
{
swap(a[i],a[j]);
i++; j--;
}
}
if (i<ri) qs(i,ri);
if (le<j) qs(le,j);
}
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<q; 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 << q << '\n';
for (int i=0; i<q; i++)
{
f << h[i].x << ' ' << h[i].y << '\n';
}
}
main()
{
lire();
ca();
qs(0,as-1);
hull();
ecrire();
}