Pagini recente » Cod sursa (job #1871169) | Cod sursa (job #2195355) | Cod sursa (job #1253608) | Cod sursa (job #2827115) | Cod sursa (job #1148584)
#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 (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(v[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=v[1];
int ind=1;
for(i=2;i<=n;i++)
{
if( (v[i].x < first.x) || ( (v[i].x == first.x) && (v[i].y < first.y) ) )
{
first=v[i];
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]=v[1];
sol[2]=v[2];
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--;
sol[++nrp]=v[i];
}
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;
}