Pagini recente » Cod sursa (job #243562) | Cod sursa (job #1584649) | Cod sursa (job #129471) | Cod sursa (job #1512566) | Cod sursa (job #902927)
Cod sursa(job #902927)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define nmax 120005
#define ll long long
#define Eps 0.000000000001
#define inf (1<<30)
int n, St[nmax];
typedef struct{
double x, y;
}camp;
camp v[nmax], Pct;
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.x = v[i].x; Pct.y = v[i].y;
poz = i;
}else if ( modul(Pct.x - v[i].x) < Eps ){
if (Pct.y > v[i].y){
Pct.x = v[i].x; Pct.y = v[i].y;
poz = i;
}
}
}
swap(v[1], v[poz]);
}
struct cmp{
bool operator()(camp A, camp B){
return( (A.x - Pct.x)*(B.y-Pct.y) < (A.y-Pct.y)*(B.x - Pct.x) );
}
};
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(){
sort(v+2, v+n+1, cmp());// pe pozitia 1 e pct ales si pe el nu are rost sa il sortez
//acum le am sortate; 1 punct e ala ales; (cel mai din stanga si cel mai de jos)
// il iau pe urmatorul si apoi il iau pe al 3 si tot incep sa scot puncte cat timp sunt in stiva cel putin 2
St[ ++St[0] ] = 1; St[ ++St[0] ] = 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;
}