Pagini recente » Cod sursa (job #880695) | Cod sursa (job #2264184) | Cod sursa (job #771996) | Cod sursa (job #1053182) | Cod sursa (job #2910375)
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
typedef pair<double,double> punct;
const int N = 120002;
int n;
punct P[N],O,H[N];
punct vect(punct A)
{
return make_pair(A.X-O.X,A.Y-O.Y);
}
double lung(punct A)
{
return sqrt(A.X*A.X+A.Y*A.Y);
}
double dist(punct A,punct B)
{
return sqrt((B.X-A.X)*(B.X-A.X)+(B.Y-A.Y)*(B.Y-A.Y));;
}
double unghi(punct A)
{
return atan2(A.Y,A.X);
}
bool crit(punct A,punct B)
{
A=vect(A);
B=vect(B);
double alfa=unghi(A);
double beta=unghi(B);
if(alfa<beta)return true;
if(beta<alfa)return false;
return lung(A)<lung(B);
}
bool elimin(punct A,punct B,punct C)
{
/// sunt in punctul A si privesc spre B
/// daca vad punctul in dreapta trebuie sa elimin
/// daca vad punctul in stanga nu trebuie sa elimin
/// daca punctele sunt coliniare
/// daca B este mai aproape de A elimin
/// daca B este mai departe de A pastrez
double delta=A.X*B.Y+B.X*C.Y+C.X*A.Y-A.Y*B.X-B.Y*C.X-C.Y*A.X;
if(delta<0)return true;
if(delta>0)return false;
if(dist(A,B)<dist(A,C)) return true;
return false;
}
int main()
{
f>>n;
for(int i=0; i<n; i++)
{
double x,y;
f>>x>>y;
P[i]=make_pair(x,y);
}
/// se alege cel mai "mic" punct
int j=0;
for(int i=1; i<n; i++)
if(P[i]<P[j])
j=i;
/// se pune punctul pe pozitia 0
swap(P[0],P[j]);
O=P[0];
/// se ordoneaza punctele dupa unghi luand drept reper P[0]
sort(P+1,P+n,crit);
/// punem in stiva primele doua puncte
H[0]=P[0];
H[1]=P[1];
int m=1;
/// consideram urmatoarele puncte
/// scoatem din stiva
for(int i=2;i<n;i++)
{
/// cat timp am doua puncte in stiva
/// si urmatorul punct se vede spre dreapta
/// se scoate ultimul punct din stiva
while(m>0 && elimin(H[m-1],H[m],P[i]))
m--;
m++;H[m]=P[i];
}
g<<m+1<<'\n';
for(int i=0;i<=m;i++)
g<<fixed<<setprecision(12)<<H[i].X<<' '<<H[i].Y<<'\n';
return 0;
}