#37107 (C++11) No.245 貫け！

提出ソース

結果

問題	No.245 貫け！
ユーザー	pekempey
提出日時	2015-07-17 22:29:00
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	37 ms / 5,000 ms
コード長	7,820 bytes
コンパイル時間	1,600 ms
コンパイル使用メモリ	172,296 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-08 08:28:45
合計ジャッジ時間	2,387 ms
ジャッジサーバーID （参考情報）	judge4 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	1 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	1 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	1 ms 6,944 KB
testcase_07	AC	1 ms 6,944 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	4 ms 6,944 KB
testcase_10	AC	5 ms 6,940 KB
testcase_11	AC	14 ms 6,940 KB
testcase_12	AC	35 ms 6,940 KB
testcase_13	AC	35 ms 6,940 KB
testcase_14	AC	33 ms 6,940 KB
testcase_15	AC	35 ms 6,940 KB
testcase_16	AC	37 ms 6,940 KB
testcase_17	AC	36 ms 6,944 KB
testcase_18	AC	36 ms 6,940 KB
testcase_19	AC	37 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
using namespace std;
typedef long long ll;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double eps = 1e-5;

struct Point {
    double x, y;
    Point() : x(0), y(0) {}
    Point(double x, double y) : x(x), y(y) {}
    double norm() { return x * x + y * y; }
    double abs() { return sqrt(norm()); }
    double arg() { return atan2(y, x); }
    double dot(Point p) { return x * p.x + y * p.y; }
    double cross(Point p) { return x * p.y - y * p.x; }
    Point operator +(Point p) { return Point(x + p.x, y + p.y); }
    Point operator -(Point p) { return Point(x - p.x, y - p.y); }
    Point operator *(double k) { return Point(x * k, y * k); }
    Point operator /(double k) { return Point(x / k, y / k); }
    static Point polar(double r, double a) { return Point(r * cos(a), r * sin(a)); }
    static double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; }
    static double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; }
};

struct Segment {
    Point p1, p2;
    Segment(double x1, double y1, double x2, double y2) : p1(x1, y1), p2(x2, y2) {}
    Segment(Point p1, Point p2) : p1(p1), p2(p2) {}
    Point project(Point p) {
        Point base = p2 - p1;
        double r = Point::dot(p - p1, base) / base.norm();
        return p1 + base * r;
    }
};

struct Circle {
    Point c;
    double r;
    Circle() : c(0, 0), r(0) {}
    Circle(double x, double y, double r) : c(x, y), r(r) {}
};

typedef Segment Line;
typedef vector<Point> Polygon;

Point normal(Point p) {
    return Point(-p.y, p.x);
}

double abs(Point p) {
    return p.abs();
}

pair<Point, Point> intersection(Circle c1, Circle c2) {
    double d = (c1.c - c2.c).abs();
    double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d));
    double t = (c2.c - c1.c).arg();
    return make_pair(c1.c + Point::polar(c1.r, t + a), c1.c + Point::polar(c1.r, t - a));
}

double distanceLP(Line l, Point p) {
    return abs((l.p2 - l.p1).cross(p - l.p1) / (l.p2 - l.p1).abs());
}

double distanceSP(Segment s, Point p) {
    if ((s.p2 - s.p1).dot(p - s.p1) < 0.0) return (p - s.p1).abs();
    if ((s.p1 - s.p2).dot(p - s.p2) < 0.0) return (p - s.p2).abs();
    return distanceLP(s, p);
}

int ccw(Point p0, Point p1, Point p2) {
    Point a = p1 - p0;
    Point b = p2 - p0;

    if (Point::cross(a, b) > eps) return 1;
    if (Point::cross(a, b) < -eps) return -1;
    if (Point::dot(a, b) < -eps) return 2;
    if (a.norm() < b.norm()) return -2;

    return 0;
}

bool intersectsL(Point p1, Point p2, Point p3, Point p4) {
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0;
}

bool intersects(Point p1, Point p2, Point p3, Point p4) {
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) <= 0 &&
           ccw(p3, p4, p1) * ccw(p3, p4, p2) <= 0;
}

bool intersects2(Point p1, Point p2, Point p3, Point p4) {
    return ccw(p1, p2, p3) * ccw(p1, p2, p4) < 0 &&
           ccw(p3, p4, p1) * ccw(p3, p4, p2) < 0;
}

bool intersects(Segment s1, Segment s2) {
    return intersects(s1.p1, s1.p2, s2.p1, s2.p2);
}

double distance(Segment s1, Segment s2) {
    if (intersects(s1, s2)) return 0;
    return min(min(distanceSP(s1, s2.p1), distanceSP(s1, s2.p2)),
               min(distanceSP(s2, s1.p1), distanceSP(s2, s1.p2)));
}

Point intersection(Segment s1, Segment s2) {
    Point base = s2.p2 - s2.p1;
    double d1 = abs(Point::cross(base, s1.p1 - s2.p1));
    double d2 = abs(Point::cross(base, s1.p2 - s2.p1));
    double t = d1 / (d1 + d2);
    return s1.p1 + (s1.p2 - s1.p1) * t;
}

bool intersectsE(Circle c, Line l) {
    return distanceLP(l, c.c) <= c.r + eps;
}

bool intersects(Circle c, Line l) {
    return distanceLP(l, c.c) < c.r - eps;
}

pair<Point, Point> intersection(Circle c, Line l) {
    Point pr = l.project(c.c);
    Point e = (l.p2 - l.p1) / (l.p2 - l.p1).abs();
    double base = sqrt(c.r * c.r - (pr - c.c).norm());
    return make_pair(pr + e * base, pr - e * base);
}

int contains(Polygon &ps, Point p) {
    int n = ps.size();
    bool even = false;
    for (int i = 0; i < n; i++) {
        Point a = ps[i] - p, b = ps[(i + 1) % n] - p;
        if (abs(Point::cross(a, b)) < eps && Point::dot(a, b) < eps) return 1;
        if (a.y > b.y) swap(a, b);
        if (a.y < eps && eps < b.y && Point::cross(a, b) > eps) even = !even;
    }
    return even ? 2 : 0;
}

struct Rectangle {
    double x1, y1, x2, y2, h;

    Rectangle() : x1(0), y1(0), x2(0), y2(0) {}
    Rectangle(double x1, double y1, double x2, double y2) : x1(x1), y1(y1), x2(x2), y2(y2) {}

    Rectangle expand(double dx, double dy) {
        return Rectangle(x1 - dx, y1 - dy, x2 + dx, y2 + dy);
    }
};

bool contains(Point p, Rectangle rc) {
    return rc.x1 + eps < p.x && p.x < rc.x2 - eps && rc.y1 + eps < p.y && p.y < rc.y2 - eps;
}

bool intersects(Point p1, Point p2, Rectangle rc) {
    if (contains(p1, rc)) return true;
    if (contains(p2, rc)) return true;

    if (intersects2(p1, p2, Point(rc.x1, rc.y1), Point(rc.x1, rc.y2))) return true;
    if (intersects2(p1, p2, Point(rc.x1, rc.y2), Point(rc.x2, rc.y2))) return true;
    if (intersects2(p1, p2, Point(rc.x2, rc.y2), Point(rc.x2, rc.y1))) return true;
    if (intersects2(p1, p2, Point(rc.x2, rc.y1), Point(rc.x1, rc.y1))) return true;

    return false;
}

bool intersects(Segment s, Circle c) {
    return distanceSP(s, c.c) < c.r - eps;
}

Point normalize(Point p) {
    return p / p.abs();
}

Point rot(Point p, double cost, double sint) {
    Point q;
    q.x = p.x * cost - p.y * sint;
    q.y = p.x * sint + p.y * cost;
    return q;
}

vector<Point> tangent(Point p, Circle c) {
    Point d = normalize(c.c - p);
    double dist = (c.c - p).abs();
    double sint = c.r / dist;
    double cost = sqrt(1 - sint * sint);

    double len = sqrt(dist * dist - c.r * c.r);

    vector<Point> res;

    res.push_back(p + rot(d, cost, sint) * len);
    res.push_back(p + rot(d, cost, -sint) * len);

    return res;
}

vector<Line> common_tangent(Circle p, Circle q) {
    double pr = p.r, qr = q.r;
    Point pc = p.c, qc = q.c;
    double d = abs(pc - qc), dr = abs(pr - qr), sr = abs(pr + qr);

    vector<Line> ret;
    if (d > sr) {
        // cross pair
        Point cp = (pc * qr + qc * pr) / sr;
        vector<Point> pts = tangent(cp, p), qts = tangent(cp, q);
        ret.push_back(Line(pts[0], qts[0]));
        ret.push_back(Line(pts[1], qts[1]));
    } else if (abs(d - sr) < eps) {
        // cross pair coinside
        Point cp = (pc * qr + qc * pr) / sr;
        ret.push_back(Line(cp, cp));
    } 

    if (d > dr) {
        // outer pair
        if (abs(pr - qr) < eps) {
            Point v = (qc - pc) / d;
            v = normal(v);
            ret.push_back(Line(pc + v, qc + v));
            ret.push_back(Line(pc - v, qc - v));
        } else {
            Point cp = pc + (qc - pc) * pr / (pr - qr);
            vector<Point> pts = tangent(cp, p), qts = tangent(cp, q);
            ret.push_back(Line(pts[0], qts[0]));
            ret.push_back(Line(pts[1], qts[1]));
        }
    } else if (abs(d - dr) < eps) {
        // outer pair coinside
        Point cp = (qc - pc) * pr / (pr - qr);
        ret.push_back(Line(cp, cp));
    } 

    return ret;
}

int N;
Point ps[200];

int main() {
    cin >> N;
    rep (i, N) {
        double a, b, c, d;
        cin >> a >> b >> c >> d;
        ps[i * 2] = Point(a, b);
        ps[i * 2 + 1] = Point(c, d);
    }

    int ans = 0;

    rep (i, N * 2) {
        rep (j, N * 2) {
            int c = 0;
            rep (k, N) {
                if (intersectsL(ps[i], ps[j], ps[k * 2], ps[k * 2 + 1])) {
                    c++;
                }
            }
            ans = max(ans, c);
        }
    }

    cout << ans << endl;
    
    return 0;
}

yukicoder

結果

テストケース

ソースコード