Pagini recente » Cod sursa (job #1831403) | Cod sursa (job #840059) | Cod sursa (job #1959287) | Cod sursa (job #323771) | Cod sursa (job #672905)
Cod sursa(job #672905)
#include<fstream>
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
#define pb push_back
int n;
stack<int> x;
stack<int> y;
vector<int> sol[100000];
struct punct{
double x;
double y;
};
punct pun[100000];
bool cmp(punct a,punct b){
if(a.y<b.y)
return true;
if(a.y==b.y && a.x<b.x)
return true;
return false;
}
void dr( int ul, int pen, double &a, double &b, double &c) {
a=pun[ul].y-pun[pen].y;
b=pun[pen].x-pun[ul].x;
c=pun[ul].x*pun[pen].y-pun[pen].x*pun[ul].y;
}
int main(){
int i,j;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(i=1;i<=n;i++)
f>>pun[i].x>>pun[i].y;
sort(pun,pun+n+1,cmp);
x.push(1);
x.push(2);
int ul=2,pen=1;
for(i=3;i<=n;i++){
double a,b,c;
dr( ul, pen, a, b, c);
while((pun[i].y-pun[pen].y)*(pun[pen].x-pun[ul].x)-(pun[i].x-pun[pen].x)*(pun[ul].y-pun[pen].x)>0 && x.size()>2){
ul=pen;
x.pop();
x.pop();
pen=x.top();
x.push(ul);
dr( ul, pen, a, b, c);
}
if(a*pun[i].x+b*pun[i].y+c>0){
x.pop();
pen=x.top();
ul=i;
x.push(i);
}
else{
x.push(i);
pen=ul;
ul=i;
}
}
y.push(1);
y.push(2);
ul=2,pen=1;
for(i=3;i<=n;i++){
double a,b,c;
dr( ul, pen, a, b, c);
while((pun[i].y-pun[pen].y)*(pun[pen].x-pun[ul].x)-(pun[i].x-pun[pen].x)*(pun[ul].y-pun[pen].x)<0 && y.size()>2){
ul=pen;
y.pop();
y.pop();
pen=y.top();
y.push(ul);
dr( ul, pen, a, b, c);
}
if(a*pun[i].x+b*pun[i].y+c<0){
y.pop();
pen=y.top();
ul=i;
y.push(i);
}
else{
y.push(i);
pen=ul;
ul=i;
}
}
int sol[100000],ct=0,lol[100000];
while(x.size()){
ct++;
lol[ct]=x.top();
x.pop();
}
for(i=ct;i>0;i--){
sol[ct-i+1]=lol[i];
}
y.pop();
while(y.size()>1){
ct++;
sol[ct]=y.top();
y.pop();
}
g<<ct<<"\n";
for(i=1;i<=ct;i++){
g<<pun[sol[i]].x<<" "<<pun[sol[i]].y<<"\n";
}
return 0;
}