?? run.cpp
字號:
/*
* Author: momodi(gaoyunxiang.cpp@gmail.com)
* 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;
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -