Cod sursa(job #2226165)

Utilizator alexandru2001alexandru alexandru2001 Data 29 iulie 2018 19:44:34
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
int afis[140000];
int n;
struct vct{
double x,y;};
vct v[140000];
bool cmp(vct A, vct B){
    if (A.y==B.y)
        return A.x<B.x;
    else
        return A.y<B.y;
}
int intoarcere(int x, int y, int z){
double delta,a1,a2,a3,b1,b2,b3;
    a1=v[x].x; b1=v[x].y;
    a2=v[y].x; b2=v[y].y;
    a3=v[z].x; b3=v[z].y;
    delta=a1*b2+a2*b3+a3*b1-a3*b2-a1*b3-a2*b1;
    if(delta>=0)
        return 1;
    else
        return 0;
}




int main()
{
  ifstream f("infasuratoare.in");
  ofstream g("infasuratoare.out");
f>>n;
for (int i=1; i<=n;i++){
    f>>v[i].x>>v[i].y;
}
sort(v+1, v+1+n, cmp);
afis[1]=1;
afis[2]=2;
int t=2;
for(int i=3; i<=n;i++){
    if (intoarcere(afis[t-1],afis[t],i)==0){afis[++t]=i;}
    else{
        while(intoarcere(afis[t-1],afis[t],i)==1&&t>=2)
            t--;
            afis[++t]=i;

    }
}
afis[++t]=n-1;
for(int i=n-2; i>=1;i--){
    if (intoarcere(afis[t-1],afis[t],i)==0){afis[++t]=i;}
    else{
        while(intoarcere(afis[t-1],afis[t],i)==1&&t>=2)
            t--;
            afis[++t]=i;

    }
}
g<<t-1<<'\n';
    for(int i=1;i<t;i++)
        g<<fixed<<setprecision(6)<<v[afis[i]].x<<' '<<fixed<<setprecision(6)<<v[afis[i]].y<<'\n';


    return 0;
}