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

Re:我来拯救你们了,如果自认为代码没问题,那么过了这几组数据,不AC你找我!

Posted by liuzimingc at 2024-07-27 11:51:34 on Problem 2826
In Reply To:我来拯救你们了,如果自认为代码没问题,那么过了这几组数据,不AC你找我! Posted by:ecjtu_yuweiwei at 2014-07-21 15:51:47
哈哈,所有数据 + 补充数据都过了,还是 WA /ll

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <vector>
#include <cassert>
 
using namespace std;

namespace liuzimingc {
#define endl '\n'
const int N = 505;
const double eps = 1e-6;

int T, n;

bool equal(double a, double b = 0) { return fabs(a - b) < eps; }

struct point {
	double x, y;
	
	point(double a = 0, double b = 0) { x = a, y = b; }
	
	void input() { cin >> x >> y; }
		
	friend point operator +(point a, point b) { return point(a.x + b.x, a.y + b.y); }
	
	friend point operator -(point a, point b) { return point(a.x - b.x, a.y - b.y);	}
	
	friend point operator *(point a, double b) { return point(a.x * b, a.y * b); }
	
	friend point operator /(point a, double b) { return point(a.x / b, a.y / b); }
	
	friend double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
	
	friend double operator *(point a, point b) { return a.x * b.y - a.y * b.x; }
	
	friend bool operator ==(point a, point b) { return equal(a.x, b.x) && equal(a.y, b.y); }
};
struct segment {
	point v[2];
	
	segment(point a = point(), point b = point()) { v[0] = a, v[1] = b; }
	
	void input() { v[0].input(), v[1].input(); }
	
	friend bool operator ==(segment a, segment b) {
		return a.v[0] == b.v[0] && a.v[1] == b.v[1]; // note
	}
	
	bool include(point p) {
		return equal((v[0] - p) * (v[1] - p)) && dot(v[0] - p, v[1] - p) <= 0;
	}
	
	bool intersect(segment s) {
		if (equal((v[0] - s.v[0]) * (v[1] - s.v[0])) && equal((v[0] - s.v[1]) * (v[1] - s.v[1]))) {
			return include(s.v[0]) || include(s.v[1]);
		}
		return ((v[1] - v[0]) * (s.v[0] - v[0])) * ((v[1] - v[0]) * (s.v[1] - v[0])) <= 0 && ((s.v[1] - s.v[0]) * (v[0] - s.v[0])) * ((s.v[1] - s.v[0]) * (v[1] - s.v[0])) <= 0;
	} // note???
	
	double dis() { return sqrt(pow(v[0].x - v[1].x, 2) + pow(v[0].y - v[1].y, 2)); }
} a, b;
struct line {
	point v[2];
	
	line(point a = point(), point b = point()) { v[0] = a, v[1] = b; }
	
	void input() { v[0].input(), v[1].input(); }
	
	bool include(point p) {
		return equal((v[0] - p) * (v[1] - p));
	}
	
	bool intersect(segment s) {
		return ((v[0] - s.v[0]) * (v[1] - s.v[0])) * ((v[0] - s.v[1]) * (v[1] - s.v[1])) <= 0;
	} // note about -1 / 1?
	
	bool intersect(line l) {
		return !equal((v[0] - v[1]) * (l.v[0] - l.v[1]));
		// return (v[0] - v[1]) * (l.v[0] - l.v[1]) < 0;
	}
	
	point intersection(line l) {
		double s1 = (l.v[0] - v[0]) * (l.v[1] - v[0]), s2 = (l.v[1] - v[1]) * (l.v[0] - v[1]);
		return v[0] + (v[1] - v[0]) * s1 / (s1 + s2);
	}
};

bool check(point l, point r, point x) {
	double k = (r.y - l.y) / (r.x - l.x);
	double b = l.y - l.x * k;
	double y = k * x.x + b;
	double ll = l.x, rr = r.x;
	if (ll > rr) swap(ll, rr);
	return y >= x.y && ll <= x.x && x.x <= rr;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		a.input(), b.input();
		if (a.v[0].y > a.v[1].y) swap(a.v[0], a.v[1]);
		if (b.v[0].y > b.v[1].y) swap(b.v[0], b.v[1]);
		if (!a.intersect(b)) {
			cout << fixed << setprecision(2) << 0.0 << endl;
			continue;
		}
		if (equal(a.v[0].y, a.v[1].y) || equal(b.v[0].y, b.v[1].y)) {
			cout << fixed << setprecision(2) << 0.0 << endl;
			continue;
		}
		if (a == b) {
			cout << fixed << setprecision(2) << 0.0 << endl;
			continue;
		}
		if (a.v[1].y < b.v[1].y) swap(a, b); // a > b v[1] > v[0]
		line al = line(a.v[0], a.v[1]), bl = line(b.v[0], b.v[1]);
		point p = al.intersection(bl);
		if (check(a.v[1], p, b.v[1])) {
			cout << fixed << setprecision(2) << 0.0 << endl;
			continue;
		}
		line bb = line(b.v[1], point(b.v[1].x + 1, b.v[1].y));
		point q = al.intersection(bb);
		cout << fixed << setprecision(2) << fabs(q.x - b.v[1].x) * (b.v[1].y - p.y) / 2 + eps << endl;
	}
	return 0;
}
#undef int
} // namespace liuzimingc
    
int main() {
	liuzimingc::main();
	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