Cod sursa(job #1837492)

Utilizator danutbodbodnariuc danut danutbod Data 29 decembrie 2016 19:28:09
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.94 kb
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <fstream>
using namespace std;
#define MAXN 120003
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct punct
{
    double x,y;
}P[MAXN];
double det(punct a,punct b, punct c){
  return ((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
}
bool cmp(punct a,punct b)
{
    return det(P[1],a,b)>0;
}
int n,xmini=2e9,ymini=2e9,p_mini,st[MAXN],vf;
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>P[i].x>>P[i].y;
    //det. punctul cel mai din stanga jos
    //determinam punctul cu x-ul cel mai mic (daca sunt mai multe puncte)
    //cel cu x-ul cel mai mic si cu y-ul cel mai mic
    for(int i=1;i<=n;i++)
        if(P[i].x<xmini)xmini=P[i].x;
    for(int i=1;i<=n;i++)
        if(P[i].x==xmini&&P[i].y<ymini) {ymini=P[i].y;p_mini=i;}
    swap(P[1],P[p_mini]); //punem punctul cel mai din stanga jos pe prima pozitie
    sort(P+2,P+n+1,cmp); //sortam dupa unghiul polar
    st[1]=1;
    st[2]=2;
    vf=2;
    for(int i=3;i<=n;i++)
    {
        while(vf>=2&&det(P[st[vf-1]],P[st[vf]],P[i])<=0)//cu <0 ia si punctele coliniare!!!
            vf--; //cat timp noul punct se infasoara invers trigonometric peste punctele din stiva
        st[++vf]=i;
    }
    if(vf>=2&&det(P[st[vf-1]],P[st[vf]],P[1])<=0)vf--;
    g<<vf<<'\n';
    for(int i=1;i<=vf;i++)
        g<<fixed<<setprecision(6)<<P[st[i]].x<<' '<<P[st[i]].y<<'\n';
    return 0;
}
//#include <iostream>
//#include <iomanip>
//#include <algorithm>
//#include <fstream>
//using namespace std;
//#define MAXN 120003
//ifstream f("infasuratoare.in");
//ofstream g("infasuratoare.out");
//struct punct
//{
//    double x,y;
//}P[MAXN];
//double det(punct a,punct b, punct c){
//  return ((a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y));
//}
//bool cmp(punct a,punct b)
//{
//    return det(P[0],a,b)>0;
//}
//int n,xmini=2e9,ymini=2e9,p_mini,st[MAXN],vf;
//int main()
//{
//    f>>n;
//    for(int i=0;i<n;i++)
//        f>>P[i].x>>P[i].y;
//    //det. punctul cel mai din stanga jos
//    //determinam punctul cu x-ul cel mai mic (daca sunt mai multe puncte)
//    //cel cu x-ul cel mai mic si cu y-ul cel mai mic
//    for(int i=0;i<n;i++)
//        if(P[i].x<xmini)xmini=P[i].x;
//    for(int i=0;i<n;i++)
//        if(P[i].x==xmini&&P[i].y<ymini) {ymini=P[i].y;p_mini=i;}
//    swap(P[0],P[p_mini]); //punem punctul cel mai din stanga jos pe prima pozitie
//    sort(P+1,P+n,cmp); //sortam dupa unghiul polar
//    P[n]=P[0];
//    st[0]=0;
//    st[1]=1;
//    vf=1;
//    for(int i=2;i<=n;i++)
//    {
//        while(vf>0&&det(P[st[vf-1]],P[st[vf]],P[i])<=0)//cu <0 ia si punctele coliniare!!!
//            vf--; //cat timp noul punct se infasoara invers trigonometric peste punctele din stiva
//        st[++vf]=i;
//    }
//    g<<vf<<'\n';
//    for(int i=1;i<=vf;i++)
//        g<<fixed<<setprecision(6)<<P[st[i]].x<<' '<<P[st[i]].y<<'\n';
//    return 0;
//}