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