結果

問題 No.245 貫け！
ユーザー 沙耶花沙耶花
提出日時 2022-03-17 20:12:34
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 324 ms / 5,000 ms
コード長 4,197 bytes
コンパイル時間 3,915 ms
コンパイル使用メモリ 267,012 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-01 19:14:07
合計ジャッジ時間 7,478 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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;
}
0