Cod sursa(job #3206933)

Utilizator nicholas9onicaOnica Nicholas Andrei nicholas9onica Data 24 februarie 2024 14:45:40
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.98 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include<cmath>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct Punct
{
    double x,y;
};
Punct punctul_vietii;
int distanta(Punct a)
{
    return (a.x-0)*(a.x-0)+(a.y-0)*(a.y-0);
}
int cadran(Punct a)
{
    if(a.x>0 && a.y>=0)
        return 1;
    else if(a.x<=0 && a.y>0)
        return 2;
    else if(a.x<0 && a.y<=0)
        return 3;
    else if(a.x>=0 && a.y<0)
        return 4;
}
int cross_product(Punct &a, Punct &b)
{
    return punctul_vietii.x*a.y+a.x*b.y+punctul_vietii.y*b.x-a.y*b.x-b.y*punctul_vietii.x-a.x*punctul_vietii.y;
}
bool cmp(Punct a,Punct b)
{
  //  if(cadran(a)==cadran(b))
  //{
  //      if(cross_product(a,b)==0)
 //           return distanta(a)<distanta(b);
        return cross_product(a,b)>0;
 //   }   
//return cadran(a)<cadran(b);
}
Punct v[101];
vector<Punct>st;
long long minst=100000,minj=100000;
int main()
{
    int i,j,n,poz;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].x>>v[i].y;
        if(v[i].x<minst)
        {
            minst=v[i].x;
            punctul_vietii=v[i];
            poz=i;
        }
        else if(v[i].x==minst && v[i].y<minj)
        {
            minj=v[i].y;
            punctul_vietii=v[i];
            poz=i;
                
        }
    }
    cout<<punctul_vietii.x<< " "<<punctul_vietii.y<<"\n";
    swap(v[1],v[poz]);
    sort(v+2,v+n+1,cmp);
    st.push_back(v[1]);
    for(i=2;i<=n;i++)
    {
        while(!st.empty() && cross_product(st.back(),v[i])<0)
        {
            st.pop_back();
        }
        st.push_back(v[i]);
    }

    for(int i=1;i<=n;i++)
    {
        cout<<v[i].x<<" "<<v[i].y<<"\n";
    }
    fout<<st.size()<<"\n";
//    fout<<punctul_vietii.x<<" "<<punctul_vietii.y<<"\n";
    
    for(i=0;i<st.size();i++)
    {
        fout<<st[i].x<<" "<<st[i].y<<'\n';
    }
    return 0;
}