Pagini recente » Cod sursa (job #2770488) | Cod sursa (job #879801) | Cod sursa (job #3178191) | Cod sursa (job #1597307) | Cod sursa (job #2152503)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define nmax 120003
int n,solutie[nmax];
struct punct
{
double x,y,panta;
} point[nmax];
void Read()
{
f>>n;
for(int i=1; i<=n; ++i)
f>>point[i].x>>point[i].y;
}
bool cmp( punct a, punct b)
{
return a.panta<b.panta;
}
/// Functia determinant folosita sa compare doua unghiuri,returneaza pozitiv daca C se afla in stanga dreptei AB
double determinant(punct A, punct B, punct C)
{
return (A.x*B.y + B.x*C.y + C.x*A.y) - (B.y*C.x + A.y*B.x + A.x*C.y);
}
double calculare_panta(double x1, double x2, double y1, double y2)
{
double numarator=y2-y1;
double numitor=x2-x1;
if(numitor==0)
{
if(numarator<0) return numeric_limits<double>::min();
if(numarator>0) return numeric_limits<double>::max();
}
return numarator/numitor;
}
void Infasuratoare()
{
int pozitie=1;
///cautare cel mai din stanga jos punct
for(int i=2; i<=n; ++i)
if(point[i].x<point[pozitie].x || point[i].x==point[pozitie].x && point[i].y<point[pozitie].y) pozitie=i;
swap(point[1],point[pozitie]);///primul punct este acum cel mai din stanga si cel mai de jos
point[1].panta=-numeric_limits<double>::max();///panta primului punct cu el insusi
for(int i=2; i<=n; ++i)///calcularea pantei fiecarei dreapte avand ca extremitati punctul 1 si punctul i
point[i].panta=calculare_panta(point[1].x,point[i].x,point[1].y,point[i].y);
sort(point+1,point+n+1,cmp);///sortare puncte in functie de panta
solutie[++solutie[0]]=1;
point[n+1]=point[1];
for(int i=1; i<=n; ++i)
{
while(solutie[0]>1 && determinant(point[solutie[solutie[0]-1]], point[i], point[solutie[solutie[0]]] )>= 0)
--solutie[0];
solutie[++solutie[0]]=i;
}
}
void Write()
{
g<<solutie[0]<<'\n';
g << fixed << setprecision(12);
for(int i=1; i<=solutie[0]; ++i)
g<<point[solutie[i]].x<<" "<<point[solutie[i]].y<<'\n';
}
int main()
{
Read();
Infasuratoare();
Write();
return 0;
}