Pagini recente » Cod sursa (job #2037298) | Cod sursa (job #2480036)
#include <bits/stdc++.h>
#define INF 1e9+7
#define LINf 1e18+7
#define fr first
#define sc second
#define ll long long
#define pb push_back
#define pii pair<int,int>
using namespace std;
vector< pair<double,double> > pn;
pair<double,double> up[200005],dw[200005];
int pu , pd;
int n;
int tr(pair<double,double> a , pair<double,double> b , pair<double,double> c){
if(a.fr*b.sc + b.fr*c.sc + c.fr*a.sc - a.fr*c.sc - b.fr*a.sc - c.fr*b.sc < 0)return -1;
return 1;
}
void psu(pair<double,double> nx){
if(pu < 2){
pu++;
up[pu] = nx;
}else{
if(tr(up[pu-1],up[pu],nx) == -1){
pu--;
psu(nx);
}else{
pu++;
up[pu] = nx;
}
}
}
void psd(pair<double,double> nx){
if(pd < 2){
pd++;
dw[pd] = nx;
}else{
if(tr(dw[pd-1],dw[pd],nx) == 1){
pd--;
psd(nx);
}else{
pd++;
dw[pd] = nx;
}
}
}
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
fin >> n;
double x, y;
for(int i = 1; i <= n ; i++){
fin >> x >> y;
pn.pb({x,y});
}
sort(pn.begin(),pn.end());
pu = 1, pd = 1;
up[pu] = pn[0];
dw[pd] = pn[0];
for(int i = 1 ; i < n - 1 ; i++){
if(tr(pn[0],pn[i],pn[n-1])==1){
psu(pn[i]);
}else{
psd(pn[i]);
}
}
psu(pn[n-1]);
psd(pn[n-1]);
fout << setprecision(12);
fout << pu + pd - 2 << '\n';
for(int i = 2 ; i <= pu ; i++){
fout << up[i].fr << " " << up[i].sc << '\n';
}
for(int i = pd - 1; i > 1 ; i--){
fout << dw[i].fr << " " << dw[i].sc << '\n';
}
}