Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

实在查不出什么错,谁能帮我看一下或侧一下?谢谢

Posted by T15 at 2005-10-16 21:05:42 on Problem 2595
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator