結果

問題 No.245 貫け！
ユーザー 沙耶花
提出日時 2022-03-17 20:12:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 372 ms / 5,000 ms
コード長 4,197 bytes
コンパイル時間 3,910 ms
コンパイル使用メモリ 257,304 KB
最終ジャッジ日時 2025-01-28 10:01:39
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define Inf 1000000001
const double eps = 1e-10;
template <typename T>
struct point{
    T x,y,rad,dir;
    
    point(T a=0.0,T b=0.0){
        x = a;
        y = b;
        fix_rd();
    }
    
    void update_x(T a,T b){
        x = a*x + b;
        fix_rd();
    }
    
    void update_x(T a){
        update_x(0.0,a);
    }
    
    void update_y(T a,T b){
        y = a*y + b;
        fix_rd();
    }
    
    void update_y(T a){
        update_y(0.0,a);
    }
    
    void update_rad(T a,T b){
        rad = a*rad + b;
        fix_xy();
    }
    
    void update_rad(T a){
        update_rad(0.0,a);
    }
    
    void update_dir(T a,T b){
        dir = a*dir + b;
        fix_xy();
    }
    void update_dir(T a){
        update_dir(0.0,a);
    }
    
    void fix_xy(){
        x = rad * cos(dir);
        y = rad * sin(dir);
        fix_rd();
    }
    
    void fix_rd(){
        rad = hypot(x,y);
        if(rad==0.0)dir=0.0;
        else dir = atan2(y,x);
        fix_zero();
    }
    
    void fix_zero(){
        if(abs(x)<eps)x = 0.0;
        if(abs(y)<eps)y = 0.0;
        if(abs(rad)<eps)rad = 0.0;
        if(abs(dir)<eps)dir = 0.0;
    }
    
    void normalize(){
        T s = size();
        update_x(1.0/s,0.0);
        update_y(1.0/s,0.0);
    }
    
    
    T get_dis(point<T> V){
        return hypot(x-V.x,y-V.y);
    }
    
    T size(){
        return get_dis(point<T>());
    }
    
    T angle_difference(point<T> V){
        double ret = dir - V.dir;
        if(ret<-acos(-1.0))ret = acos(-1.0)*2.0+ret;
        if(ret>acos(-1.0))ret=-acos(-1.0)*2.0+ret;
        return ret;
    }
    
    //中点
    point get_midpoint(point<T> V){
        V.update_x(0.5,x/2.0);
        V.update_y(0.5,y/2.0);
        return V;
    }
    
    T get_inner_product(point<T> V){
        return x*V.x+y*V.y;
    }
    
    T get_cross_product(point<T> V){
        return x*V.y-y*V.x;
    }
    
    point &operator+=(const point<T> &another){
        update_x(1,another.x);
        update_y(1,another.y);
        return (*this);
    }
    
    point &operator-=(const point<T> &another){
        update_x(1,-another.x);
        update_y(1,-another.y);
        return (*this);
    }
    
    point operator+(const point<T> &another)const{
        return (point(*this)+=another);
    }
    
    point operator-(const point<T> &another)const{
        return (point(*this)-=another);
    }
    
    void show(){
        cout<<x<<','<<y<<endl;
    }
};
//a+tx
template <typename T>
struct line{
    point<T> a,t;
    
    line(point<T> V1,point<T> V2){
        a=V1;
        t=V2-V1;
    }
    T get_signed_dis(point<T> V){
        point<double> PA = a-V;
        return PA.get_cross_product(t)/t.size();
    }
    
    T get_dis(point<T> V){
        return abs(get_signed_dis(V));
    }
    
    point<T> get_projection(point<T> P){
        T r = t.get_inner_product(P-a)/t.size();
        point<T> temp = t;
        temp.update_rad(0.0,r);
        return a+temp;
    }   
    
    point<T> get_cross_point(line<T> L){
        point<T> ret(1e20,1e20);
        if(abs(t.get_cross_product(L.t))<eps)return ret;
        T d0 = L.get_signed_dis(a);
        T d1 = L.get_signed_dis(a+t);
        point<T> temp = t;
        temp.x *= d0/(d1-d0);
        temp.y *= d0/(d1-d0);
        ret = a - temp;
        return ret;
    }
    
};
template <typename T>
struct segment{
    point<T> V1,V2;
    segment(point<T> a=point<T>(),point<T> b=point<T>()){
        V1=a;
        V2=b;
    }
    
    T get_dis(point<T> P){
        T ret = 1e20;
        line<T> L(V1,V2);
        point<T> Q = L.get_projection(P);
        if(Q.x+eps>min(V1.x,V2.x)&&Q.y+eps>min(V1.y,V2.y)
        &&Q.x<max(V1.x,V2.x)+eps&&Q.y<max(V1.y,V2.y)+eps)ret = min(ret,Q.get_dis(P));
        else{
            ret = min(ret,P.get_dis(V1));
            ret = min(ret,P.get_dis(V2));
        }
        return ret;
    }
    
    T get_dis(segment<T> l){
        if(get_cross_point(l).x<1e20)return 0.0;
        return min({get_dis(l.V1),get_dis(l.V2),l.get_dis(V1),l.get_dis(V2)});
    }
    
    point<T> get_cross_point(segment<T> l){
        line<T> L1(V1,V2),L2(l.V1,l.V2);
        point<T> P = L1.get_cross_point(L2);
        if(get_dis(P)<eps&&l.get_dis(P)<eps)return P;
        return point<T> (1e20,1e20);
    }
};
int main(){
    int n;
    cin>>n;
    vector<segment<double>> S;
    vector<point<double>> t;
    rep(i,n){
        
        double x,y;cin>>x>>y;
        point<double> a(x,y);
        cin>>x>>y;
        point<double> b(x,y);
        S.push_back(segment<double>(a,b));
        
        t.push_back(a);
        t.push_back(b);
    }
    
    int ans = 0;
    rep(i,t.size()){
        for(int j=i+1;j<t.size();j++){
            line<double> l(t[i],t[j]);
            int tt = 0;
            rep(k,n){
                if(l.get_signed_dis(S[k].V1) * l.get_signed_dis(S[k].V2)<eps)tt++;
            }
            ans = max(ans,tt);
        }
    }
    
    cout<<ans<<endl;
            
    
    
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0