| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
实在查不出什么错,谁能帮我看一下或侧一下?谢谢#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAX_N = 50010;
const double MAX_NUM = 1e+20;
const double ZERO = 1e-6;
struct Point {
int x, y;
};
inline int sqr(int a) {
return a * a;
}
int dis(int x1, int y1, int x2, int y2) {
return sqr(x1 - x2) + sqr(y1 - y2);
}
int multi(int x1, int y1, int x2, int y2) {
return x1 * y2 - x2 * y1;
}
class pre {
Point bot;
public:
pre(const Point& p) {
bot = p;
}
bool operator()(const Point& p1, const Point& p2) {
int mul = multi(p1.x - bot.x, p1.y - bot.y, p2.x - bot.x, p2.y - bot.y);
return mul > 0 || mul == 0 && dis(bot.x, bot.y, p1.x, p1.y) < dis(bot.x, bot.y, p2.x, p2.y);
}
};
Point p[MAX_N];
int t[MAX_N];
int n, C, top;
double lower, upper;
bool input_data() {
int i;
if (scanf("%d %d", &n, &C) == EOF) return false;
for (i = 0; i < n; i++) scanf("%d", &p[i].x);
for (i = 0; i < n; i++) scanf("%d", &p[i].y);
return true;
}
void check(double y) {
if (y < lower) lower = y;
if (y > upper) upper = y;
}
void solve() {
int i;
if (n == 1) {
lower = upper = p[0].y;
return;
}
for (i = 1; i < n; i++) {
if (p[i].y < p[0].y || p[i].y == p[0].y && p[i].x < p[0].x) swap(p[0], p[i]);
}
sort(p + 1, p + n, pre(p[0]));
t[0] = 0; t[1] = 1; top = 2;
for (i = 2; i < n; i++) {
while (top >= 2 && pre(p[t[top - 2]])(p[i], p[t[top - 1]])) top--;
t[top++] = i;
}
lower = MAX_NUM; upper = -MAX_NUM;
for (i = 0; i < top; i++) {
Point& p1 = p[t[i]];
Point& p2 = p[t[(i + 1) % top]];
if ((p1.x - C) * (p2.x - C) <= 0) {
if (p1.x == p2.x) {
check(p1.y);
check(p2.y);
}
else {
check((double)((p1.y - p2.y) * C + (p1.x * p2.y - p2.x * p1.y)) / (p1.x - p2.x));
}
}
}
}
void output_data() {
if (abs(lower) <= ZERO) lower = 0;
if (abs(upper) <= ZERO) upper = 0;
if (lower > upper) while (true);
printf("%.3lf %.3lf\n", lower, upper);
}
int main() {
while (input_data()) {
solve();
output_data();
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator