Pagini recente » Cod sursa (job #940761) | Cod sursa (job #2421471) | Cod sursa (job #1100155) | Cod sursa (job #369420) | Cod sursa (job #1869782)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define ct 0.000000000001
int n,r,use[120110],k,i,pas;
int stiva[120100];
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
double x,y;
}v[120100],A,B;
int comp(punct A,punct B)
{
return (A.y<B.y ||(A.y==B.y && A.x<B.x));
}
void coeficienti(punct A,punct B,double &aa,double &bb,double &cc)
{
aa=A.y-B.y;
bb=B.x-A.x;
cc=A.x*B.y-A.y*B.x;
}
void modific()
{
if(pas==1)
{
i++;
if(i==n)pas=-1;
}
else i--;
}
int semn(punct A,punct B,punct C)
{
double aa,bb,cc;
coeficienti(A,B,aa,bb,cc);
if(aa*C.x+bb*C.y+cc<=0) return -1;
return 1;
}
void acoperire()
{
double u,umin;
sort(v+1,v+n+1,comp);
pas=1; stiva[1]=1; stiva[2]=2;use[2]=1;
k=2;i=2;///punctul curent
while(i>1)
{
while(use[i])modific();
if(i==0) break;
while(k>1 && semn(v[stiva[k-1]],v[stiva[k]],v[i])==-1)
{
use[stiva[k]]=0;/// deselectare
k--;///scot din stiva
}
k++; stiva[k]=i; use[i]=1;
}
g<<k-1<<endl;
for(i=1;i<=k-1;i++){g<<fixed<<setprecision(6)<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<endl;}
}
int main()
{
f>>n;
for(i=1;i<=n;i++) f>>v[i].x>>v[i].y;
acoperire();
return 0;
}
/*
12
1 1
11 1
11 20
1 20
4 5
1.5 6
5 5
5 2
5 8
10 16
20 5
8 45
*/