結果

問題 No.245 貫け！
ユーザー koyoprokoyopro
提出日時 2015-10-06 10:46:47
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,796 bytes
コンパイル時間 2,030 ms
コンパイル使用メモリ 161,516 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-20 01:40:24
合計ジャッジ時間 2,692 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 WA -
testcase_05 AC 2 ms
5,376 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 4 ms
5,376 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 14 ms
5,376 KB
testcase_17 AC 16 ms
5,376 KB
testcase_18 WA -
testcase_19 AC 15 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;

#define REP(i, n) for(int i=0; i<(n); i++)
struct P {
    int x, y;
    P(){};
    P(int _x, int _y): x(_x), y(_y){};

    P operator * (int t) {
        return P(t * x, t * y);
    }
    P operator + (P q) {
        return P(x + q.x, y + q.y);
    }
    P operator - (P q) {
        return P(x - q.x, y - q.y);
    }
    int dot(P q) {
        return x * q.x + y * q.y;
    }
    int det(P q) {
        return x * q.y - y * q.x;
    }
};

int N;
vector<pair<P,P> > ps;

bool is_cross(P a, P b, P c, P d) {
    P v1 = a - b;
    P v2 = c - b;
    P v3 = d - b;
    if (v1.det(v2) * v1.det(v3) > 0) return false;
    v1 = b - a;
    v2 = c - a;
    v3 = d - a;
    if (v1.det(v2) * v1.det(v3) > 0) return false;
    v1 = c - d;
    v2 = a - d;
    v3 = b - d;
    if (v1.det(v2) * v1.det(v3) > 0) return false;
    v1 = d - d;
    v2 = a - d;
    v3 = b - d;
    if (v1.det(v2) * v1.det(v3) > 0) return false;
    return true;
}

int count(P p, P q) {
    int cnt = 0;
    // TODO:
    // 線分の存在する範囲が[-200, 200]なので、それを越える線分を作る→交差判定
    P v = p - q;
    int vx = (v.x) ? abs(500 / v.x) : 1e5;
    int vy = (v.y) ? abs(500 / v.y) : 1e5;
    int times = min(vx, vy);
    q = q + (v * times);
    p = p - (v * times);
    REP(i,N) {
        cnt += is_cross(p, q, ps[i].first, ps[i].second);
    }
    return cnt;
}

signed main()
{
    cin >> N;
    ps.resize(N);
    REP(i,N) {
        cin >> ps[i].first.x >> ps[i].first.y;
        cin >> ps[i].second.x >> ps[i].second.y;
    }
    int maxc = 0;
    REP(i,N) REP(j,N) {
        if (i == j) continue;
        P p = ps[i].first;
        P q = ps[j].second;
        maxc = max(maxc, count(p, q));
    }
    cout << maxc << endl;
    return 0;
}
0