Cod sursa(job #2291165)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 27 noiembrie 2018 18:41:59
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <stack>
#include <iomanip>
#define MAX 120010

using namespace std;
typedef double db;

int n,pi,p1,p2,p3;
int vi[MAX];
db x[MAX],y[MAX];
stack<int> ans;
vector<int> ansf;
bool test;

bool cmp(int i, int j) { // comparam tangentele
  return (x[j] - x[pi]) * (y[i] - y[pi]) < (x[i] - x[pi]) * (y[j] - y[pi]);
}

double semn (int i1, int i2, int i3) { // aria cu semn a triunghiului
  return x[i1] * y[i2] + x[i2] * y[i3] + x[i3] * y[i1] - y[i1] * x[i2] - y[i2] * x[i3] - y[i3] * x[i1];
}

int main()
{
    ifstream f ("infasuratoare.in");
    ofstream g ("infasuratoare.out");
    f>>n;
    pi=1;
    for(int i=1;i<=n;i++){
      f>>x[i]>>y[i];
      vi[i]=i;
      if(x[i]<x[pi])pi=i;
    }
    swap(x[1],x[pi]); swap(y[1],y[pi]);
    sort(vi+2,vi+n+1,cmp); vi[n+1]=vi[1];
    ans.push(1),ans.push(2);
    for(int i=3;i<=n+1;i++){
      do{
        test=0;
        p2=ans.top();
        ans.pop(),p1=ans.top(),ans.push(p2);
        p3=vi[i];
        if(semn(p1,p2,p3)<0){
          ans.pop();
          test=1;
        }
      } while(test);
      ans.push(vi[i]);
    }
    ans.pop();
    g<<ans.size()<<'\n';
    while(ans.size()){
      //cout<<ans.top()<<" ";
      //g<<fixed<<setprecision(6)<<x[ans.top()]<<" "<<y[ans.top()]<<'\n';
      ansf.push_back(ans.top());
      ans.pop();
    }
    pi=0;
    sort(ansf.begin(),ansf.end(),cmp);
    for(auto i:ansf)
      g<<fixed<<setprecision(6)<<x[i]<<" "<<y[i]<<'\n';
    f.close ();
    g.close ();
    return 0;
}