Cod sursa(job #1420263)

Utilizator azkabancont-vechi azkaban Data 18 aprilie 2015 00:35:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f3
int n;
double a,b;
struct point 
        {
         double x,y,panta;
		} p[120013];
vector < point > St;
struct comp 
      {
     bool operator() (const point &a,const point &b)
        {
         return (a.panta<b.panta);
		}
	  };
double det(point a,point b,point c) 
 {
 return (a.x*b.y - a.y*b.x + 
         b.x*c.y - c.x*b.y + 
		 c.x*a.y - a.x*c.y );
 }
int main(void)
{
 ifstream cin("infasuratoare.in");
 ofstream cout("infasuratoare.out");
 cin>>n;
 int poz=1;
 for (int i=1;i<=n;++i)
    {
     cin>>a>>b;
     p[i]={a,b};
     if (a<p[poz].x || (a==p[poz].x && b<p[poz].y))  poz=i;
	}
 swap(p[poz],p[1]);
 for (int i=2;i<=n;++i) 
     if (p[i].x==p[1].x) p[i].panta=inf;
                    else p[i].panta=(p[i].y-p[1].y)/(p[i].x-p[1].x);
 sort(p+2,p+n+1,comp());
 St.push_back(p[1]);
 St.push_back(p[2]);
 for (int i=3;i<=n;++i) 
    {
     while (!St.empty() && det(St[St.size()-1],St[St.size()-2],p[i])>=0) St.pop_back(); 
     St.push_back(p[i]);
    }
 cout<<St.size()<<"\n";
 for (int i=0;i<St.size();++i) 
   cout<<fixed<<setprecision(13)<<St[i].x<<" "<<St[i].y<<"\n";
 return 0;
}