Cod sursa(job #945366)

Utilizator VictorVrabieVrabie Victor VictorVrabie Data 1 mai 2013 19:10:32
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 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;
    }
 
    printf("%d\n", t + 1);
    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;
}
*/