Pagini recente » Cod sursa (job #1142081) | Cod sursa (job #3270958) | Cod sursa (job #342698) | Cod sursa (job #2539811) | Cod sursa (job #2641685)
#include <bits/stdc++.h>
#define det(a,b,c,d,e,f) a*d+b*e+c*f-e*d-a*f-c*b
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
pair<long double, long double> a[120010];
stack<int> St;
long double dist(long double a0,long double a1,long double b0,long double b1){
return sqrt((b0-a0)*(b0-a0)+(b1-a1)*(b1-a1));
}
pair<long double,long double> caos(pair<long double, long double> A){
return {(a[1].second-A.second)/dist(A.first,A.second,a[1].first,a[1].second),dist(A.first,A.second,a[1].first,a[1].second)};
}
bool comp(pair<long double, long double> A,pair<long double, long double> B){
return (caos(A)>caos(B));
}
bool ok(int poz){
int B=St.top();St.pop();
int A=St.top();St.push(B);
return (det(a[A].first,a[A].second,a[B].first,a[B].second,a[poz].first,a[poz].second)<=0);
}
int main(){
f>>n;
for(int i=1;i<=n;i++){
f>>a[i].first>>a[i].second;
}
sort(a+1,a+n+1);
sort(a+2,a+n+1,comp);
St.push(1);
St.push(2);
for(int i=3;i<=n;i++){
while(St.size()>=2&&ok(i))
St.pop();
St.push(i);
}
vector<int> v;
while(St.size()){
v.push_back(St.top());
St.pop();
}
reverse(v.begin(),v.end());
g<<v.size()<<'\n';
for(auto it:v)
g<<fixed<<setprecision(6)<<a[it].first<<' '<<a[it].second<<'\n';
}