Pagini recente » Cod sursa (job #627517) | Cod sursa (job #1936342) | Cod sursa (job #2813481) | Cod sursa (job #624063) | Cod sursa (job #1091631)
#include<fstream>
#include<algorithm>
#include<deque>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct QQ{
double x;
double y;
double p;
};
bool cmp1(QQ i, QQ j){
if(i.x==j.x)
return i.y<j.y;
else
return i.x<j.x;
}
bool cmp2(QQ i, QQ j){
return i.p<j.p;
}
QQ a[100005];
deque<int> b;
int main(){
int n,i,j,x1,y1,k,q,w;
double m;
f>>n;
for(i=1; i<=n; ++i){
f>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1, cmp1);
x1=a[1].x; y1=a[1].y;
for(i=2; i<=n; ++i){
a[i].p=(a[i].y-y1)/(a[i].x-x1);
}
sort(a+2, a+n+1,cmp2);
a[n+1]=a[1];
b.push_back(1);
b.push_back(2);
b.push_back(3);
if(n>3){
for(i=1; i<n-1; ++i){
k=b[b.size()-3];
q=b[b.size()-2];
w=b.back();
m=(a[q].y-a[k].y)*(a[w].x - a[q].x) - (a[w].y - a[q].y)*(a[q].x - a[k].x);
if(m>0){
b[b.size()-2]=b.back();
b.pop_back();
b.push_back(b.back()+1);
}
else{
b.push_back(b.back()+1);
}
}
b.pop_back();
}
g<<b.size()<<"\n";
for(i=0; i<b.size(); ++i){
g<<a[b[i]].x<<" "<<a[b[i]].y<<"\n";
}
return 0;
}