Cod sursa(job #944290)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 28 aprilie 2013 00:03:22
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.74 kb
#include <cstdio>
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <ctype.h>
#include <cstring>
#include <ctime>
#include <cassert>
#include <utility>

using namespace std;

#define x first
#define y second
typedef double val_t;
typedef pair<val_t, val_t> Point;

#define MAXN 120005

Point P[MAXN];
int N;
int st[MAXN];

inline val_t crossProduct(const Point &A, const Point &B, const Point &C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

bool cmp(const Point &A, const Point &B) {
    return crossProduct(P[0], A, B) > 0;
}

int main() {
	freopen("infasuratoare.in", "r", stdin);
	freopen("infasuratoare.out","w", stdout);

    scanf("%d\n", &N);

    int first = 0;
    for(int i = 0; i < N; i++) {
        scanf("%lf", &P[i].x);
        scanf("%lf", &P[i].y);
        if(P[i].x < P[first].x)
            first = i;
    }


    swap(P[0], P[first]);
    sort(P + 1, P + N, cmp);

    int t = 1;
    st[0] = 0;
    st[1] = 1;

    for(int i = 2; i < N; i++) {
        while(t > 0 && crossProduct(P[ st[t - 1] ], P[ st[t] ], P[i]) < 0)
            t--;
        st[++t] = i;
    }

    for(int i = 0; i <= t; i++)
        printf("%.12lf %.12lf\n", P[ st[i] ].x, P[ st[i] ].y);

//    double area = 0.0;
//    for(int i = 1; i < t; i++)
//        area += crossProduct(P[ st[0] ], P[ st[i] ], P[ st[i + 1] ]);
//    area /= 2.0;
//
//    printf("%.2lf\n", area);

	return 0;
}

/*#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <algorithm>
#define DN 10005
#define x first
#define y second
#define LL long long
using namespace std;

typedef pair<LL,LL> per;

int n;
per p[DN];
vector<per> v;

LL det(per a,per b,per c) {
    LL sum=b.x*c.y+c.x*a.y+a.x*b.y;
    LL dif=-a.x*c.y-b.x*a.y-c.x*b.y;
    return sum+dif;
}

LL arie(vector<per> p) {
  LL r=0;
  for(int i=2; i<p.size(); ++i) r+=det(p[i-1],p[i],p[0]);
  return r;
}

int main()
{
    ifstream f("livada.in");
    ofstream g("livada.out");
    f>>n;
    for(int i=0; i<n; ++i) f>>p[i].x;
    for(int i=0; i<n; ++i) f>>p[i].y;
    sort(p,p+n);
    v.push_back(p[0]); v.push_back(p[1]);
    for(int i=2; i<n; ++i) {
      for(;v.size()>1 && det(v[v.size()-2],v.back(),p[i])<0;v.pop_back());
      v.push_back(p[i]);
    }
    for(int i=n-1;i>=0; --i) {
      for(;v.size()>1 && det(v[v.size()-2],v.back(),p[i])<0;v.pop_back());
      v.push_back(p[i]);
    }
    v.pop_back();
    g<<fixed<<setprecision(2)<<arie(v)*0.5;
    return 0;
}
*/