| ||||||||||
| 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 | |||||||||
Re:我来拯救你们了,如果自认为代码没问题,那么过了这几组数据,不AC你找我!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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator