run.cpp

第四届百度杯编程大赛final解题报告+标程

/*
 * Author: momodi([e-mail])
 * Created Time:  2009/3/24 12:11:47
 * File Name: run.cpp
 * Description: 
 */
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define out(x) fprintf(stderr, "%s: %I64d\n", #x, (long long)(x))
#define SZ(v) ((int)(v).size())
const int maxint=-1u>>1;
template <class T> bool get_max(T& a, const T &b) {return b > a? a = b, 1: 0;}
template <class T> bool get_min(T& a, const T &b) {return b < a? a = b, 1: 0;}
const double eps = 1e-9;
int sgn(const double &a) {
    return (a > eps) - (a < -eps);
}
int n;
const int maxn = 50001;

struct P {
    double a, b;
    P (const double &_a, const double &_b)
        :a(_a), b(_b) {}
    P () {}
    bool operator < (const P &i) const {
        return sgn(a - i.a) > 0;
    }
    bool operator == (const P &x) const {
        return sgn(a - x.a) == 0;
    }
};

double crossy(const P &x, const P &y) {
    return x.a * (y.b - x.b) / (x.a - y.a) + x.b;
}
double crossx(const P &x, const P &y) {
    return (y.b - x.b) / (x.a - y.a);
}

P p[maxn];
P sta[maxn];
double Y[maxn];
int solve() {
    sort(p, p + n);
//    printf("%d %d\n", unique(p, p + n) - p, n);
    if (unique(p, p + n) - p != n) {
        printf("Data Error\n");
        while (1);
    }
    int len = 0;
    int y_len = 0;
    for (int i = 0; i < n; ++i) {
        if (len == 0) {
            sta[len++] = p[i];
        } else if (len == 1) {
            sta[len++] = p[i];
            Y[y_len++] = crossy(sta[0], sta[1]);
        } else {
            double yy = crossy(sta[len - 1], p[i]);
            if (sgn(yy - Y[y_len - 1]) < 0) {
                Y[y_len++] = yy;
                sta[len++] = p[i];
            } else {
                --i;
                --len;
                --y_len;
            }
        }
    }
    while (len >= 2) {
        double xx = crossx(sta[len - 1], sta[len - 2]);
        if (sgn(xx) <= 0) {
            --len;
        } else {
            break;
        }
    }
    return len;
}


int main() {
    int ca;
    scanf("%d", &ca);
    while (ca--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            double a, b;
            scanf("%lf %lf", &b, &a);
            p[i] = P(a, b);
        }
        printf("%d\n", solve());
    }
    return 0;
}