Pagini recente » Cod sursa (job #149134) | Cod sursa (job #783773) | Cod sursa (job #1096881) | Cod sursa (job #2670315) | Cod sursa (job #2291165)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <stack>
#include <iomanip>
#define MAX 120010
using namespace std;
typedef double db;
int n,pi,p1,p2,p3;
int vi[MAX];
db x[MAX],y[MAX];
stack<int> ans;
vector<int> ansf;
bool test;
bool cmp(int i, int j) { // comparam tangentele
return (x[j] - x[pi]) * (y[i] - y[pi]) < (x[i] - x[pi]) * (y[j] - y[pi]);
}
double semn (int i1, int i2, int i3) { // aria cu semn a triunghiului
return x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
}
int main()
{
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
f>>n;
pi=1;
for(int i=1;i<=n;i++){
f>>x[i]>>y[i];
vi[i]=i;
if(x[i]<x[pi])pi=i;
}
swap(x[1],x[pi]); swap(y[1],y[pi]);
sort(vi+2,vi+n+1,cmp); vi[n+1]=vi[1];
ans.push(1),ans.push(2);
for(int i=3;i<=n+1;i++){
do{
test=0;
p2=ans.top();
ans.pop(),p1=ans.top(),ans.push(p2);
p3=vi[i];
if(semn(p1,p2,p3)<0){
ans.pop();
test=1;
}
} while(test);
ans.push(vi[i]);
}
ans.pop();
g<<ans.size()<<'\n';
while(ans.size()){
//cout<<ans.top()<<" ";
//g<<fixed<<setprecision(6)<<x[ans.top()]<<" "<<y[ans.top()]<<'\n';
ansf.push_back(ans.top());
ans.pop();
}
pi=0;
sort(ansf.begin(),ansf.end(),cmp);
for(auto i:ansf)
g<<fixed<<setprecision(6)<<x[i]<<" "<<y[i]<<'\n';
f.close ();
g.close ();
return 0;
}