Pagini recente » Cod sursa (job #2297085) | Cod sursa (job #2501544) | Cod sursa (job #1675991) | Cod sursa (job #1766668) | Cod sursa (job #3032232)
#include <bits/stdc++.h>
using ll=long long;
#define S second
#define F first
#define endl '\n'
#define spid ios_base::sync_with_stdio(false);cin.tie(NULL);
const int mod=1e9+7;
const double pi=3.14159265359;
const int maxn=120001;
using namespace std;
int n;
struct punct{
double x;
double y;
bool operator == (punct &X){
return x==X.x&&y==X.y;
}
}A[maxn];
punct colt;
bool compare(punct A,punct B){
double cosA=(A.x-colt.x)/sqrtl((A.x-colt.x)*(A.x-colt.x)+(A.y-colt.y)*(A.y-colt.y));
double cosB=(B.x-colt.x)/sqrtl((B.x-colt.x)*(B.x-colt.x)+(B.y-colt.y)*(B.y-colt.y));
return cosA>cosB;
}
int main(){
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
cin>>n;
for(int i=0;i<n;i++){
cin>>A[i].x;
cin>>A[i].y;
}
colt.y=A[0].y;
colt.x=A[0].x;
for(int i=1;i<n;i++){
if(A[i].y<colt.y){
colt=A[i];
}
else if(A[i].y==colt.y){
if(A[i].x<colt.x)A[i]=colt;
}
}
for(int i=0;i<n;i++){
if(A[i]==colt){
for(;i<n-1;i++){
A[i]=A[i+1];
}
}
}
sort(A,A+n-1,compare);
vector<punct> S;
S.push_back(colt);
S.push_back(A[0]);
for(int i=1;i<n-1;i++){
while(((S[S.size()-1].x-A[i].x)*(S[S.size()-2].y-A[i].y)-(S[S.size()-1].y-A[i].y)*(S[S.size()-2].x-A[i].x))>0)S.pop_back();
S.push_back(A[i]);
}
cout<<S.size()<<endl;
for(int i=0;i<S.size();i++)cout<<S[i].x<<" "<<S[i].y<<endl;
}