Cod sursa(job #1473758)

Utilizator tiby10Tibi P tiby10 Data 20 august 2015 09:44:13
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define NMAX 120005

int n;
pair<double,double> P[NMAX];
vector<int> hull;
int det(int i1, int i2, int i3) {
 int dx1 = P[i2].x-P[i1].x,
     dx2 = P[i3].x-P[i1].x,
     dy1 = P[i2].y-P[i1].y,
     dy2 = P[i3].y-P[i1].y;

    return (1LL*dx1*dy2)-(1LL*dx2*dy1);
}

void solve(){
hull.pb(1);
while(true) {
    int pi=hull.back();

    int choose=pi+1;
    if(choose==(n+1))
        choose=1;

    for(int i=1;i<=n;i++)
        if(i!=pi && det(pi,choose,i)>0)
             choose=i;

    if(choose == 1)
        break;

    hull.pb(choose);
}
}

int main() {
    ifstream fin("infasuratoare.in");
    ofstream fout("infasuratoare.out");
    fin>>n;
    for(int i=1;i<=n;++i)
        fin>>P[i].x>>P[i].y;

    solve();
    fout<<hull.size()<<'\n'<<P[hull.front()].x<<" "<<P[hull.front()].y<<'\n';
    for(vector<int>::reverse_iterator i=hull.rbegin(); i!=hull.rend()-1; ++i)
        fout<<P[*i].x<<" "<<P[*i].y<<'\n';
    return 0;
}