Pagini recente » Cod sursa (job #695150) | Cod sursa (job #1792325) | Cod sursa (job #179739) | Cod sursa (job #3292048) | Cod sursa (job #1148554)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
const int maxn = 120001;
int n;
struct point
{
double x,y;
}sol[maxn],v[maxn];
inline double cross_product(const point &a, const point &b, const point &c)
{
return (double) (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
inline bool cmp (const point& a,const point&b)
{
//return a.panta < b.panta;
return cross_product(sol[1],a,b) < 0;
}
int main()
{
in>>n;
int i;
for(i=1;i<=n;i++)
in>>v[i].x>>v[i].y;
//gaseste primul element din infasuratoare
point first;
first.y=1<<30;
first.x=1<<30;
int ind;
for(i=1;i<=n;i++)
{
if((v[i].y<first.y)||(v[i].y==first.y&&v[i].x<first.x))
{
first.y=v[i].y;
first.x=v[i].x;
ind=i;
}
}
//in v[i].panta retinem panta punctului i fata de punctul de referinta (cel mai din stanga jos)
swap(v[1],v[ind]);//punctul de referinta este pus primul in vector
/* for(i=2;i<=n;i++)
v[i].panta=(v[i].y-first.y)/(v[i].x-first.x);
*/
//sortez vectorul in functie de panta
sort(v+2,v+n+1,cmp);
//primele 2 puncte din solutie
sol[1].x=v[1].x;
sol[1].y=v[1].y;
sol[2].x=v[2].x;
sol[2].y=v[2].y;
int nrp=2;
//incercam toate punctele ramase :
//daca ultimele doua puncte bagate in solutie si punctul curent se duc la dreapta si avem mai mult sau egal de 2 puncte in solutie ( cele initiale )
//scoatem din solutie ultimul punct adauga, pana cand am ramas la 2 elemente in solutie sau merg la stanga; in acest caz adaug la solutie punctul curent
for(i=3;i<=n;i++)
{
while( nrp >= 2 && cross_product(sol[nrp-1],sol[nrp],v[i]) > 0 )
nrp--;
nrp++;
sol[nrp].x=v[i].x;
sol[nrp].y=v[i].y;
}
out<<nrp<<"\n";
out<<fixed<<setprecision(6);
out<<sol[1].x<<" "<<sol[1].y<<"\n";
for(i=nrp;i>=2;i--)
out<<sol[i].x<<" "<<sol[i].y<<"\n";
return 0;
}