Pagini recente » Cod sursa (job #2150449) | Cod sursa (job #282255) | Cod sursa (job #863965) | Cod sursa (job #685754) | Cod sursa (job #2586326)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
const int MAXN = 120000 + 2;
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef long double ld;
struct punct{
ld x,y;
}v[MAXN],stiva[MAXN];
int n,varf;
punct primul_punct;
bool cmp_puncte(punct a,punct b){
if(a.y < b.y)
return true;
if(a.y == b.y)
return a.x < b.x;
return false;
}
ld unghi(punct a,punct b){
return (a.x - b.x) / (a.y - b.y);
}
bool cmp_unghi(punct a,punct b){
if(unghi(primul_punct,a) > unghi(primul_punct,b))
return true;
return false;
}
ld cross(punct a,punct b,punct c){
ld val = (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
return val;
}
void afis(){
cout<<"Stiva : "<<"\n";
for(int i = 1; i <= varf; i++)
cout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
}
int main()
{
in>>n;
for(int i = 1; i <= n; i++)
in>>v[i].x>>v[i].y;
sort(v + 1,v + n + 1,cmp_puncte);
primul_punct = v[1];
sort(v + 2,v + n + 1,cmp_unghi);
// for(int i = 2; i <= n; i++){
// cout<<v[i].x<<" "<<v[i].y<<" cu unghiul : "<<unghi(primul_punct,v[i])<<endl;
// }
varf = 2;
stiva[1] = primul_punct;
stiva[2] = v[2];
///afis();
/// daca merg unghiul format dintre dreapta determinata de penuiltimul,ultimul si penultimul curent > 180 => nu e ok
for(int i = 3; i <= n; i++){
while(varf >= 2 && cross(stiva[varf - 1],stiva[varf],v[i]) < 0){
varf--;
}
stiva[++varf] = v[i];
}
out<<varf<<"\n";
for(int i = 1; i <= varf; i++)
out<<setprecision(13)<<fixed<<stiva[i].x<<" "<<stiva[i].y<<"\n";
return 0;
}