結果

問題 No.245 貫け！
コンテスト
ユーザー koyopro
提出日時 2015-10-06 10:56:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,795 bytes
コンパイル時間 1,571 ms
コンパイル使用メモリ 162,980 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-20 01:41:11
合計ジャッジ時間 2,351 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 WA * 12
権限があれば一括ダウンロードができます

ソースコード

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;
    // 線分の存在する範囲が[-200, 200]なので、それを越える線分を作る→交差判定
    P v = p - q;
    //int vx = (v.x) ? abs(1000 / v.x) : 1e5;
    //int vy = (v.y) ? abs(1000 / 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