Pagini recente » Cod sursa (job #1182986) | Cod sursa (job #775963) | Cod sursa (job #877731) | Cod sursa (job #650892) | Cod sursa (job #2910374)
#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;
vector<punct> H;///infasuratoarea
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.push_back(P[0]);
H.push_back(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]))
{
H.pop_back();m--;
}
H.push_back(P[i]);m++;
}
g<<H.size()<<'\n';
for(auto p:H)
g<<fixed<<setprecision(12)<<p.X<<' '<<p.Y<<'\n';
return 0;
}