test/geometory/Distance-line.test.cpp

• View this file on GitHub
• Last update: 2023-05-30 04:39:19+09:00
• Problem: https://yukicoder.me/problems/no/1041

Depends on

• Distance - 距離 (lib/70-geometory/Distance.cpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/1041"

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#include "../../lib/70-geometory/Distance.cpp"

int main(void){
    int N; cin >> N;
    vector<double> x(N),y(N);
    for(int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i];
    }
    int ans = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = i+1; j < N; ++j) {
            int cnt = 2;
            for(int k = 0; k < N; ++k){
                if(k==i || k == j) continue;
                if(Distance<long double>::between_point_and_line(x[i],y[i],x[j],y[j],x[k],y[k]) < 1e-3 ) cnt++;
            }
            ans = max(ans,cnt);
        }
    }
    cout << ans << endl;
	return 0;
}

#line 1 "test/geometory/Distance-line.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1041"

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#line 1 "lib/70-geometory/Distance.cpp"
/*
 * @title Distance - 距離
 * @docs md/geometory/Distance.md
 */
template<class T> class Distance{
public:
    //Euclidean distance
    inline static constexpr T euclid(const T& x1, const T& y1, const T& x2, const T& y2) {
        return sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
    }
    //Chebyshev distance
    inline static constexpr T chebyshev(T x1, T y1, T x2, T y2) {
        return max(abs(x1 - x2),abs(y1 - y2));
    }
    //Manhattan distance
    inline static constexpr T manhattan(T x1, T y1, T x2, T y2) {
        return abs(x1 - x2)+abs(y1 - y2);
    }
    inline static constexpr T between_point_and_line(const T& x,const T& y,const T& x1,const T& y1,const T& x2,const T& y2){
        return abs((y2 - y1)*x+(x1 - x2)*y-(y2-y1)*x1+(x2-x1)*y1)/sqrt((y2 - y1)*(y2 - y1)+(x1 - x2)*(x1 - x2));
    }
};
#line 8 "test/geometory/Distance-line.test.cpp"

int main(void){
    int N; cin >> N;
    vector<double> x(N),y(N);
    for(int i = 0; i < N; ++i) {
        cin >> x[i] >> y[i];
    }
    int ans = 0;
    for(int i = 0; i < N; ++i) {
        for(int j = i+1; j < N; ++j) {
            int cnt = 2;
            for(int k = 0; k < N; ++k){
                if(k==i || k == j) continue;
                if(Distance<long double>::between_point_and_line(x[i],y[i],x[j],y[j],x[k],y[k]) < 1e-3 ) cnt++;
            }
            ans = max(ans,cnt);
        }
    }
    cout << ans << endl;
	return 0;
}

Back to top page