Pagini recente » Arhiva de probleme | Cod sursa (job #1731643) | Cod sursa (job #2313372) | Cod sursa (job #1736653) | Cod sursa (job #934748)
Cod sursa(job #934748)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <iomanip>
using namespace std;
#define x first
#define y second
#define nmax 120005
#define Eps 0.000000000001
#define inf (1<<30)
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n, st[nmax];
pair<double, double> v[nmax], Pct;
struct cmp{
bool operator()(pair<int,int> A, pair<int,int> B){
// x1 - X / y1 - Y < x2 - X / y2 - Y => (x1 - X) * (y2-Y) < (y1-Y) * (x2-X);
return( (A.x - Pct.x)*(B.y-Pct.y) < (A.y - Pct.y)*(B.x - Pct.x) );
}
};
double modul( double x){
if (x < 0.0) return -x;
return x;
}
void citeste(){
f >> n;
int poz = 0;
Pct.x = (double)inf;Pct.y = (double)inf;
for(int i=1; i<=n; ++i){
f >> v[i].x >> v[i].y;
if (Pct.x > v[i].x){
Pct = make_pair(v[i].x, v[i].y); poz = i;
}else if ( modul( Pct.x - v[i].x) < Eps ){// x-urile sunt egale ma uit la y
if (Pct.y > v[i].y){
Pct = make_pair(v[i].x, v[i].y); poz = i;
}
}
}
swap(v[poz], v[1]);// aduc cel mai din stanga jos punct la inceputul vectorului
sort(v+2, v+n+1, cmp() );
}
inline double semn(int i , int j , int k){
return ( v[i].x*v[j].y + v[j].x*v[k].y + v[k].x*v[i].y - v[k].x*v[j].y - v[k].y*v[i].x - v[j].x*v[i].y );
}
void rezolva(){
st[0] = 2;
st[1] = 1; st[2] = 2;
for(int i=3; i<=n; ++i){
while(st[0] >= 2 && semn(st[ st[0]-1 ], st[ st[0] ], i) >= 0.000000000000){
--st[0];
}
st[ ++st[0] ] = i;
}
g << st[0] << "\n";
g << fixed;
for(int i=st[0]; i>=1; --i){
g << setprecision(12) << v[st[i]].x << " " << v[st[i]].y << "\n";
}
}
int main(){
setprecision(12);
citeste();
rezolva();
f.close();
g.close();
return 0;
}