test/aoj/2972.test.cpp

• View this file on GitHub
• Last update: 2024-09-28 19:54:09+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2972

Depends on

• 点 (src/Geometry/Point.hpp)
• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• int から long long などのテンプレート (src/Internal/long_traits.hpp)
• 黄金分割探索 (src/Optimization/golden_search.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2972
// competitive-verifier: ERROR 0.0001
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include "src/Optimization/golden_search.hpp"
#include "src/Geometry/Point.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using namespace geo;
 using R= long double;
 int N, K;
 cin >> N >> K;
 vector<Point<R>> ps(N);
 for (int i= 0; i < N; ++i) cin >> ps[i];
 auto score= [&](const Point<R> &p) {
  vector<R> dis(N);
  for (int i= 0; i < N; ++i) dis[i]= dist(ps[i], p);
  sort(dis.rbegin(), dis.rend());
  R ret= 0;
  for (int i= 0; i < K; ++i) ret+= dis[i];
  return ret;
 };
 auto f= [&](R x) {
  auto g= [&](R y) { return score({x, y}); };
  return golden_search<MINIMIZE>(g, -1000.0, 1000.0).second;
 };
 cout << fixed << setprecision(10) << golden_search<MINIMIZE>(f, -1000.0, 1000.0).second << '\n';
 return 0;
}

#line 1 "test/aoj/2972.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2972
// competitive-verifier: ERROR 0.0001
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#line 2 "src/Optimization/golden_search.hpp"
#include <cmath>
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 6 "src/Optimization/golden_search.hpp"
// [l,r]
template <MinMaxEnum obj, class F> std::pair<long double, result_type_t<F>> golden_search(const F &f, long double l, long double r, int iter= 100) {
 static constexpr long double c= 0.38196601125;
 assert(l <= r);
 long double x= l + (r - l) * c, y= r - (r - l) * c;
 result_type_t<F> fx= f(x), fy= f(y);
 for (bool g; iter--;) {
  if constexpr (obj == MINIMIZE) g= fx < fy;
  else g= fx > fy;
  if (g) r= y, y= x, fy= fx, fx= f(x= l + (r - l) * c);
  else l= x, x= y, fx= fy, fy= f(y= r - (r - l) * c);
 }
 return {x, fx};
}
#line 3 "src/Geometry/Point.hpp"
#include <fstream>
#line 2 "src/Internal/long_traits.hpp"
// clang-format off
template<class T>struct make_long{using type= T;};
template<>struct make_long<char>{using type= short;};
template<>struct make_long<unsigned char>{using type= unsigned short;};
template<>struct make_long<short>{using type= int;};
template<>struct make_long<unsigned short>{using type= unsigned;};
template<>struct make_long<int>{using type= long long;};
template<>struct make_long<unsigned>{using type= unsigned long long;};
template<>struct make_long<long long>{using type= __int128_t;};
template<>struct make_long<unsigned long long>{using type= __uint128_t;};
template<>struct make_long<float>{using type= double;};
template<>struct make_long<double>{using type= long double;};
template<class T> using make_long_t= typename make_long<T>::type;
// clang-format on
#line 8 "src/Geometry/Point.hpp"
namespace geo {
using namespace std;
struct Visualizer {
 ofstream ofs;
 Visualizer(string s= "visualize.txt"): ofs(s) { ofs << fixed << setprecision(10); }
 friend Visualizer &operator<<(Visualizer &vis, const string &s) { return vis.ofs << s, vis; }
};
template <class K> int sgn(K x) {
 if constexpr (is_floating_point_v<K>) {
  static constexpr K EPS= 1e-9;
  return x < -EPS ? -1 : x > EPS;
 } else return x < 0 ? -1 : x > 0;
}
template <class K> K err_floor(K x) {
 K y= floor(x);
 if constexpr (is_floating_point_v<K>)
  if (K z= y + 1, w= x - z; 0 <= sgn(w) && sgn(w - 1) < 0) return z;
 return y;
}
template <class K> K err_ceil(K x) {
 K y= ceil(x);
 if constexpr (is_floating_point_v<K>)
  if (K z= y - 1, w= x - z; 0 < sgn(w + 1) && sgn(w) <= 0) return z;
 return y;
}
template <class K> struct Point {
 K x, y;
 Point(K x= K(), K y= K()): x(x), y(y) {}
 Point &operator+=(const Point &p) { return x+= p.x, y+= p.y, *this; }
 Point &operator-=(const Point &p) { return x-= p.x, y-= p.y, *this; }
 Point &operator*=(K a) { return x*= a, y*= a, *this; }
 Point &operator/=(K a) { return x/= a, y/= a, *this; }
 Point operator+(const Point &p) const { return {x + p.x, y + p.y}; }
 Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
 Point operator*(K a) const { return {x * a, y * a}; }
 Point operator/(K a) const { return {x / a, y / a}; }
 friend Point operator*(K a, const Point &p) { return {a * p.x, a * p.y}; }
 Point operator-() const { return {-x, -y}; }
 bool operator<(const Point &p) const {
  int s= sgn(x - p.x);
  return s ? s < 0 : sgn(y - p.y) < 0;
 }
 bool operator>(const Point &p) const { return p < *this; }
 bool operator<=(const Point &p) const { return !(p < *this); }
 bool operator>=(const Point &p) const { return !(*this < p); }
 bool operator==(const Point &p) const { return !sgn(x - p.x) && !sgn(y - p.y); }
 bool operator!=(const Point &p) const { return sgn(x - p.x) || sgn(y - p.y); }
 Point operator!() const { return {-y, x}; }  // rotate 90 degree
 friend istream &operator>>(istream &is, Point &p) { return is >> p.x >> p.y; }
 friend ostream &operator<<(ostream &os, const Point &p) { return os << "(" << p.x << ", " << p.y << ")"; }
 friend Visualizer &operator<<(Visualizer &vis, const Point &p) { return vis.ofs << p.x << " " << p.y << "\n", vis; }
};
template <class K> make_long_t<K> dot(const Point<K> &p, const Point<K> &q) { return make_long_t<K>(p.x) * q.x + make_long_t<K>(p.y) * q.y; }
// left turn: > 0, right turn: < 0
template <class K> make_long_t<K> cross(const Point<K> &p, const Point<K> &q) { return make_long_t<K>(p.x) * q.y - make_long_t<K>(p.y) * q.x; }
template <class K> make_long_t<K> norm2(const Point<K> &p) { return dot(p, p); }
template <class K> long double norm(const Point<K> &p) { return sqrt(norm2(p)); }
template <class K> make_long_t<K> dist2(const Point<K> &p, const Point<K> &q) { return norm2(p - q); }
template <class T, class U> long double dist(const T &a, const U &b) { return sqrt(dist2(a, b)); }
enum CCW { COUNTER_CLOCKWISE, CLOCKWISE, ONLINE_BACK, ONLINE_FRONT, ON_SEGMENT };
ostream &operator<<(ostream &os, CCW c) { return os << (c == COUNTER_CLOCKWISE ? "COUNTER_CLOCKWISE" : c == CLOCKWISE ? "CLOCKWISE" : c == ONLINE_BACK ? "ONLINE_BACK" : c == ONLINE_FRONT ? "ONLINE_FRONT" : "ON_SEGMENT"); }
template <class K> CCW ccw(const Point<K> &p0, const Point<K> &p1, const Point<K> &p2) {
 Point a= p1 - p0, b= p2 - p0;
 int s;
 if constexpr (is_floating_point_v<K>) s= sgn(sgn(cross(a, b) / sqrt(norm2(a) * norm2(b))));
 else s= sgn(cross(a, b));
 if (s) return s > 0 ? COUNTER_CLOCKWISE : CLOCKWISE;
 if (K d= dot(a, b); sgn(d) < 0) return ONLINE_BACK;
 else return sgn(d - norm2(a)) > 0 ? ONLINE_FRONT : ON_SEGMENT;
}
template <class K> struct Line;
template <class K> struct Segment;
template <class K> class Polygon;
template <class K> struct Convex;
template <class K> struct Affine {
 K a00= 1, a01= 0, a10= 0, a11= 1;
 Point<K> b;
 Point<K> operator()(const Point<K> &p) const { return {a00 * p.x + a01 * p.y + b.x, a10 * p.x + a11 * p.y + b.y}; }
 Line<K> operator()(const Line<K> &l);
 Segment<K> operator()(const Segment<K> &s);
 Polygon<K> operator()(const Polygon<K> &p);
 Convex<K> operator()(const Convex<K> &c);
 Affine operator*(const Affine &r) const { return {a00 * r.a00 + a01 * r.a10, a00 * r.a01 + a01 * r.a11, a10 * r.a00 + a11 * r.a10, a10 * r.a01 + a11 * r.a11, (*this)(r)}; }
 Affine &operator*=(const Affine &r) { return *this= *this * r; }
};
template <class K> Affine<K> translate(const Point<K> &p) { return {1, 0, 0, 1, p}; }
}
#line 11 "test/aoj/2972.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 using namespace geo;
 using R= long double;
 int N, K;
 cin >> N >> K;
 vector<Point<R>> ps(N);
 for (int i= 0; i < N; ++i) cin >> ps[i];
 auto score= [&](const Point<R> &p) {
  vector<R> dis(N);
  for (int i= 0; i < N; ++i) dis[i]= dist(ps[i], p);
  sort(dis.rbegin(), dis.rend());
  R ret= 0;
  for (int i= 0; i < K; ++i) ret+= dis[i];
  return ret;
 };
 auto f= [&](R x) {
  auto g= [&](R y) { return score({x, y}); };
  return golden_search<MINIMIZE>(g, -1000.0, 1000.0).second;
 };
 cout << fixed << setprecision(10) << golden_search<MINIMIZE>(f, -1000.0, 1000.0).second << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	testcase_00	AC	7 ms	4 MB
g++-13	testcase_01	AC	6 ms	4 MB
g++-13	testcase_02	AC	7 ms	4 MB
g++-13	testcase_03	AC	6 ms	4 MB
g++-13	testcase_04	AC	7 ms	4 MB
g++-13	testcase_05	AC	7 ms	4 MB
g++-13	testcase_06	AC	7 ms	4 MB
g++-13	testcase_07	AC	6 ms	4 MB
g++-13	testcase_08	AC	6 ms	4 MB
g++-13	testcase_09	AC	7 ms	4 MB
g++-13	testcase_10	AC	6 ms	4 MB
g++-13	testcase_11	AC	6 ms	4 MB
g++-13	testcase_12	AC	6 ms	4 MB
g++-13	testcase_13	AC	41 ms	4 MB
g++-13	testcase_14	AC	17 ms	4 MB
g++-13	testcase_15	AC	72 ms	4 MB
g++-13	testcase_16	AC	42 ms	4 MB
g++-13	testcase_17	AC	14 ms	4 MB
g++-13	testcase_18	AC	21 ms	4 MB
g++-13	testcase_19	AC	63 ms	4 MB
g++-13	testcase_20	AC	58 ms	4 MB
g++-13	testcase_21	AC	7 ms	4 MB
g++-13	testcase_22	AC	39 ms	4 MB
g++-13	testcase_23	AC	5 ms	4 MB
g++-13	testcase_24	AC	6 ms	4 MB
g++-13	testcase_25	AC	68 ms	4 MB
g++-13	testcase_26	AC	76 ms	4 MB
g++-13	testcase_27	AC	71 ms	4 MB
g++-13	testcase_28	AC	72 ms	4 MB
g++-13	testcase_29	AC	70 ms	4 MB
clang++-18	testcase_00	AC	6 ms	4 MB
clang++-18	testcase_01	AC	6 ms	4 MB
clang++-18	testcase_02	AC	7 ms	4 MB
clang++-18	testcase_03	AC	6 ms	4 MB
clang++-18	testcase_04	AC	7 ms	4 MB
clang++-18	testcase_05	AC	6 ms	4 MB
clang++-18	testcase_06	AC	7 ms	4 MB
clang++-18	testcase_07	AC	6 ms	4 MB
clang++-18	testcase_08	AC	6 ms	4 MB
clang++-18	testcase_09	AC	7 ms	4 MB
clang++-18	testcase_10	AC	6 ms	4 MB
clang++-18	testcase_11	AC	6 ms	4 MB
clang++-18	testcase_12	AC	7 ms	4 MB
clang++-18	testcase_13	AC	45 ms	4 MB
clang++-18	testcase_14	AC	19 ms	4 MB
clang++-18	testcase_15	AC	77 ms	4 MB
clang++-18	testcase_16	AC	45 ms	4 MB
clang++-18	testcase_17	AC	15 ms	4 MB
clang++-18	testcase_18	AC	22 ms	4 MB
clang++-18	testcase_19	AC	67 ms	4 MB
clang++-18	testcase_20	AC	63 ms	4 MB
clang++-18	testcase_21	AC	7 ms	4 MB
clang++-18	testcase_22	AC	42 ms	4 MB
clang++-18	testcase_23	AC	7 ms	4 MB
clang++-18	testcase_24	AC	6 ms	4 MB
clang++-18	testcase_25	AC	72 ms	4 MB
clang++-18	testcase_26	AC	81 ms	4 MB
clang++-18	testcase_27	AC	75 ms	4 MB
clang++-18	testcase_28	AC	76 ms	4 MB
clang++-18	testcase_29	AC	74 ms	4 MB

Back to top page