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