Cod sursa(job #2549666)

Utilizator Lazar_LaurentiuLazar Laurentiu Lazar_Laurentiu Data 17 februarie 2020 21:38:46
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>

#define MAX 120010

#define x first
#define y second

using namespace std;
typedef long double db;

int n,imin;
pair<db,db> a[MAX],a1;
vector< pair<db,db> > ans;

bool cmp(pair<db,db> t1,pair<db,db> t2){
  db u1,u2;
  u1=(t1.y-a1.y)/(t1.x-a1.x);
  u2=(t2.y-a1.y)/(t2.x-a1.x);
  return u1<u2;
}
bool ok(pair<db,db> p1, pair<db,db> p2, pair<db,db> p3){
  if(p1.x==p2.x){
    if(p1.y<p2.y)return p3.x<p1.x;
    else return p3.x>p1.x;
  }
  bool test=0,sus;
  if(p1.x>p2.x)swap(p1,p2),test=1;
  db m,c;
  m=(p2.y-p1.y)/(p2.x-p1.x);
  c=p1.y-p1.x*m;
  if(p3.y>m*p3.x+c)sus=1;
  else sus=0;
  if(!test)return sus;
  else return !sus;
}

int main()
{
    ifstream f ("infasuratoare.in");
    ofstream g ("infasuratoare.out");
    f>>n;
    for(int i=1;i<=n;i++)
      f>>a[i].x>>a[i].y;
    imin=1;
    for(int i=2;i<=n;i++){
      if(a[i].x<a[imin].x)
        imin=i;
      else
        if(a[i].x==a[imin].x)
          if(a[i].y<a[imin].y)
            imin=i;
    }
    swap(a[1],a[imin]);
    a1=a[1];
    sort(a+2,a+n+1,cmp);
    ans.push_back(a1);
    for(int i=2;i<=n;i++){
      if(ans.size()==1){
        ans.push_back(a[i]);
        continue;
      }
      while(ans.size()>=2&&!ok(ans[ans.size()-2],ans[ans.size()-1],a[i])){
//        cout<<ans[ans.size()-2].x<<" "<<ans[ans.size()-2].y<<'\n';
//        cout<<ans[ans.size()-1].x<<" "<<ans[ans.size()-1].y<<'\n';
//        cout<<a[i].x<<" "<<a[i].y<<'\n';
//        cout<<ok(ans[ans.size()-2],ans[ans.size()-1],a[i])<<"\n\n";
        ans.pop_back();
      }
      ans.push_back(a[i]);
    }
    g<<ans.size()<<'\n';
    g<<setprecision(6)<<fixed;
    for(auto i:ans)g<<i.x<<" "<<i.y<<'\n';
//    for(int i=1;i<=n;i++)
//      cout<<a[i].x<<" "<<a[i].y<<'\n';
//    for(int i=1;i<=n;i++)
//      g<<"( "<<a[i].x<<" , "<<a[i].y<<" )\n";
//    for(int i=1;i<=100;i++)
//      g<<i<<'\n';
    f.close ();
    g.close ();
    return 0;
}