library/test/aoj/CGL_1_A-Projection.test.cpp

• View this file on GitHub
• Last update: 2024-03-15 16:42:38+06:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/CGL_1_A

Depends on

• library/geometry/2dGeometryTemplate.hpp
• library/geometry/2dPointAndVector.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/CGL_1_A"
#include <bits/stdc++.h>
using namespace std;
#include "../../geometry/2dPointAndVector.hpp"
#define ERROR 0.00000001

int main() {
    ios_base::sync_with_stdio(0);
    Point p1, p2;
    cin>>p1>>p2;
    Line l = Line(p1, p2);

    int q;
    cin>>q;
    while(q--) {
        Point p;
        cin>>p;
        cout<<projection(l, p)<<'\n';
    }
    return 0;
}

#line 1 "library/test/aoj/CGL_1_A-Projection.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/CGL_1_A"
#include <bits/stdc++.h>
using namespace std;
#line 2 "library/geometry/2dGeometryTemplate.hpp"

using Real = double;
using Point = complex<Real>;
using Polygon = vector<Point>;
const Real EPS = 1e-8, PI = acos(-1);

Point operator*(const Point& p, const Real& d) {
    return Point(p.real() * d, p.imag() * d);
}

Point operator/(const Point& p, const Real& d) {
    return Point(p.real() / d, p.imag() / d);
}

istream& operator>>(istream& is, Point& p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}

ostream& operator<<(ostream& os, const Point& p) {
    return os << fixed << setprecision(20) << p.real() << " " << p.imag();
}

int sign(const Real& r) {
    if (r <= -EPS) return -1;
    if (r >= +EPS) return +1;
    return 0;
}

bool equals(const Real& a, const Real& b) {
    return sign(a - b) == 0;
}

namespace std {
bool operator<(const Point& a, const Point& b) {
    if (equals(a.real(), b.real())) return a.imag() < b.imag();
    return a.real() < b.real();
}
}  // namespace std

Real dot(const Point& a, const Point& b) {
    return (conj(a) * b).real();
}

Real cross(const Point& a, const Point& b) {
    return (conj(a) * b).imag();
}

struct Line {
    Point a, b;
    Line() = default;
    Line(Point a, Point b) : a(a), b(b) {}
};
using Segment = Line;
#line 3 "library/geometry/2dPointAndVector.hpp"

Point projection(const Line& l, const Point& p) {
    return l.a + (l.a - l.b) * dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
}

Point reflection(const Line& l, const Point& p) {
    return p + (projection(l, p) - p) * 2.0;
}

int ccw(const Point& a, Point b, Point c) {
    b -= a, c -= a;
    if (sign(cross(b, c)) == +1) return +1; // COUNTER_CLOCKWISE
    if (sign(cross(b, c)) == -1) return -1;// CLOCKWISE
    if (sign(dot(b, c)) == -1) return +2; // ONLINE_BACK
    if (norm(b) < norm(c)) return -2; // ONLINE_FRONT
    return 0; // ON_SEGMENT
}
#line 5 "library/test/aoj/CGL_1_A-Projection.test.cpp"
#define ERROR 0.00000001

int main() {
    ios_base::sync_with_stdio(0);
    Point p1, p2;
    cin>>p1>>p2;
    Line l = Line(p1, p2);

    int q;
    cin>>q;
    while(q--) {
        Point p;
        cin>>p;
        cout<<projection(l, p)<<'\n';
    }
    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_int_00.in	AC	6 ms	4 MB
g++	00_int_01.in	AC	6 ms	4 MB
g++	00_int_02.in	AC	6 ms	4 MB
g++	00_int_03.in	AC	6 ms	4 MB
g++	00_int_04.in	AC	5 ms	4 MB
g++	00_int_05.in	AC	6 ms	4 MB
g++	01_real_00.in	AC	6 ms	4 MB
g++	01_real_01.in	AC	5 ms	4 MB
g++	02_online_00.in	AC	6 ms	4 MB
g++	02_online_01.in	AC	6 ms	4 MB
g++	02_online_02.in	AC	6 ms	4 MB
g++	02_online_03.in	AC	5 ms	4 MB
g++	03_horizontal_00.in	AC	6 ms	4 MB
g++	03_horizontal_01.in	AC	6 ms	4 MB
g++	04_vertical_00.in	AC	6 ms	4 MB
g++	04_vertical_01.in	AC	6 ms	4 MB
g++	05_rand_00.in	AC	6 ms	4 MB
g++	05_rand_01.in	AC	6 ms	4 MB
g++	05_rand_02.in	AC	6 ms	4 MB
g++	05_rand_03.in	AC	8 ms	4 MB
g++	05_rand_04.in	AC	8 ms	4 MB
g++	05_rand_05.in	AC	8 ms	4 MB
g++	05_rand_06.in	AC	8 ms	4 MB
g++	05_rand_07.in	AC	9 ms	4 MB
g++	05_rand_08.in	AC	12 ms	4 MB
g++	05_rand_09.in	AC	12 ms	4 MB
g++	05_rand_10.in	AC	9 ms	4 MB
g++	05_rand_11.in	AC	11 ms	4 MB
g++	05_rand_12.in	AC	9 ms	4 MB
g++	05_rand_13.in	AC	9 ms	4 MB
g++	05_rand_14.in	AC	9 ms	4 MB
g++	05_rand_15.in	AC	8 ms	4 MB

Back to top page