#line 1 "test/aoj/2136/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2136"
#include <iostream>
#include <vector>
#line 2 "Mylib/Geometry/Float/double_eps.cpp"
#include <cmath>
#line 4 "Mylib/Geometry/Float/double_eps.cpp"
#include <limits>
namespace haar_lib {
template <typename T, const T &eps>
struct double_eps {
using value_type = T;
private:
T value_;
public:
double_eps() : value_(0) {}
double_eps(T value_) : value_(value_) {}
auto &operator=(const double_eps &rhs) {
this->value_ = rhs.value_;
return *this;
}
auto &operator+=(const double_eps &rhs) {
this->value_ += rhs.value_;
return *this;
}
auto &operator-=(const double_eps &rhs) {
this->value_ -= rhs.value_;
return *this;
}
auto &operator*=(const double_eps &rhs) {
this->value_ *= rhs.value_;
return *this;
}
auto &operator/=(const double_eps &rhs) {
this->value_ /= rhs.value_;
return *this;
}
auto operator+(const double_eps &rhs) const { return double_eps(this->value_ + rhs.value_); }
auto operator-(const double_eps &rhs) const { return double_eps(this->value_ - rhs.value_); }
auto operator*(const double_eps &rhs) const { return double_eps(this->value_ * rhs.value_); }
auto operator/(const double_eps &rhs) const { return double_eps(this->value_ / rhs.value_); }
bool operator==(const double_eps &rhs) const { return std::abs(this->value_ - rhs.value_) < eps; }
bool operator!=(const double_eps &rhs) const { return !(*this == rhs); }
bool operator<(const double_eps &rhs) const { return this->value_ - rhs.value_ < -eps; }
bool operator<=(const double_eps &rhs) const { return this->value_ - rhs.value_ < eps; }
bool operator>(const double_eps &rhs) const { return !(*this <= rhs); }
bool operator>=(const double_eps &rhs) const { return !(*this < rhs); }
auto operator-() const { return double_eps(-(this->value_)); }
explicit operator double() const noexcept { return value_; }
explicit operator long double() const noexcept { return value_; }
friend std::ostream &operator<<(std::ostream &s, const double_eps &rhs) {
s << rhs.value_;
return s;
}
friend std::istream &operator>>(std::istream &s, double_eps &rhs) {
s >> rhs.value_;
return s;
}
friend double_eps sin(double_eps x) { return std::sin((T) x); }
friend double_eps cos(double_eps x) { return std::cos((T) x); }
friend double_eps tan(double_eps x) { return std::tan((T) x); }
friend double_eps acos(double_eps x) { return std::acos((T) x); }
friend double_eps atan2(double_eps y, double_eps x) { return std::atan2((T) y, (T) x); }
friend double_eps abs(double_eps x) { return std::abs((T) x); }
friend double_eps sqrt(double_eps x) { return std::sqrt(std::max<T>(0, (T) x)); }
};
} // namespace haar_lib
namespace std {
template <typename T, const T &eps>
class numeric_limits<haar_lib::double_eps<T, eps>> {
public:
static haar_lib::double_eps<T, eps> infinity() { return numeric_limits<T>::infinity(); }
static haar_lib::double_eps<T, eps> min() { return numeric_limits<T>::min(); }
static haar_lib::double_eps<T, eps> max() { return numeric_limits<T>::max(); }
static haar_lib::double_eps<T, eps> lowest() { return numeric_limits<T>::lowest(); }
};
} // namespace std
#line 5 "Mylib/Geometry/Float/geometry_template.cpp"
namespace haar_lib {
template <typename T>
struct vec {
T x, y;
vec() {}
vec(T x, T y) : x(x), y(y) {}
friend auto operator+(const vec &a, const vec &b) { return vec(a.x + b.x, a.y + b.y); }
friend auto operator-(const vec &a, const vec &b) { return vec(a.x - b.x, a.y - b.y); }
friend auto operator-(const vec &a) { return vec(-a.x, -a.y); }
friend bool operator==(const vec &a, const vec &b) { return a.x == b.x and a.y == b.y; }
friend bool operator!=(const vec &a, const vec &b) { return !(a == b); }
friend bool operator<(const vec &a, const vec &b) { return a.x < b.x or (a.x == b.x and a.y < b.y); }
friend std::istream &operator>>(std::istream &s, vec &a) {
s >> a.x >> a.y;
return s;
}
};
template <typename T, typename U>
auto operator*(const vec<T> &a, const U &k) { return vec<T>(a.x * k, a.y * k); }
template <typename T, typename U>
auto operator*(const U &k, const vec<T> &a) { return vec<T>(a.x * k, a.y * k); }
template <typename T, typename U>
auto operator/(const vec<T> &a, const U &k) { return vec<T>(a.x / k, a.y / k); }
template <typename T>
using point = vec<T>;
template <typename T>
T abs(const vec<T> &a) { return sqrt(a.x * a.x + a.y * a.y); }
template <typename T>
T abs_sq(const vec<T> &a) { return a.x * a.x + a.y * a.y; }
template <typename T>
T dot(const vec<T> &a, const vec<T> &b) { return a.x * b.x + a.y * b.y; }
template <typename T>
T cross(const vec<T> &a, const vec<T> &b) { return a.x * b.y - a.y * b.x; }
template <typename T>
auto unit(const vec<T> &a) { return a / abs(a); }
template <typename T>
auto normal(const vec<T> &p) { return vec<T>(-p.y, p.x); }
template <typename T>
auto polar(const T &r, const T &ang) { return vec<T>(r * cos(ang), r * sin(ang)); }
template <typename T>
T angle(const vec<T> &a, const vec<T> &b) { return atan2(b.y - a.y, b.x - a.x); }
template <typename T>
T phase(const vec<T> &a) { return atan2(a.y, a.x); }
template <typename T>
T angle_diff(const vec<T> &a, const vec<T> &b) {
T r = phase(b) - phase(a);
if (r < -M_PI)
return r + 2 * M_PI;
else if (r > M_PI)
return r - 2 * M_PI;
return r;
}
template <typename T>
struct line {
point<T> from, to;
line() : from(), to() {}
line(const point<T> &from, const point<T> &to) : from(from), to(to) {}
};
template <typename T>
using segment = line<T>;
template <typename T>
auto unit(const line<T> &a) { return unit(a.to - a.from); }
template <typename T>
auto normal(const line<T> &a) { return normal(a.to - a.from); }
template <typename T>
auto diff(const segment<T> &a) { return a.to - a.from; }
template <typename T>
T abs(const segment<T> &a) { return abs(diff(a)); }
template <typename T>
T dot(const line<T> &a, const line<T> &b) { return dot(diff(a), diff(b)); }
template <typename T>
T cross(const line<T> &a, const line<T> &b) { return cross(diff(a), diff(b)); }
template <typename T>
using polygon = std::vector<point<T>>;
template <typename T>
struct circle {
point<T> center;
T radius;
circle() : center(), radius(0) {}
circle(const point<T> ¢er, T radius) : center(center), radius(radius) {}
};
template <typename T>
std::ostream &operator<<(std::ostream &s, const vec<T> &a) {
s << "(" << a.x << ", " << a.y << ")";
return s;
}
template <typename T>
std::ostream &operator<<(std::ostream &s, const line<T> &a) {
s << "(" << a.from << " -> " << a.to << ")";
return s;
}
template <typename T>
std::ostream &operator<<(std::ostream &s, const circle<T> &a) {
s << "("
<< "center: " << a.center << ", "
<< "radius: " << a.radius << ")";
return s;
}
} // namespace haar_lib
#line 3 "Mylib/Geometry/Float/ccw.cpp"
namespace haar_lib {
namespace ccw_impl {
enum status {
ONLINE_BACK = -2,
COUNTER_CLOCKWISE = -1,
ON_SEGMENT = 0,
CLOCKWISE = 1,
ONLINE_FRONT = 2
};
}
struct ccw {
ccw_impl::status value;
bool operator==(const ccw &that) const { return value == that.value; };
bool operator!=(const ccw &that) const { return value != that.value; };
bool is_online_back() const { return value == ccw_impl::status::ONLINE_BACK; }
bool is_counter_clockwise() const { return value == ccw_impl::status::COUNTER_CLOCKWISE; }
bool is_on_segment() const { return value == ccw_impl::status::ON_SEGMENT; }
bool is_clockwise() const { return value == ccw_impl::status::CLOCKWISE; }
bool is_online_front() const { return value == ccw_impl::status::ONLINE_FRONT; }
};
template <typename T>
ccw check_ccw(const point<T> &p0, const point<T> &p1, const point<T> &p2) {
using namespace ccw_impl;
const T cr = cross(p1 - p0, p2 - p0);
const T d = dot(p1 - p0, p2 - p0);
if (cr == 0) {
if (d < 0)
return ccw({ONLINE_BACK});
else if (abs(p2 - p0) > abs(p1 - p0))
return ccw({ONLINE_FRONT});
else
return ccw({ON_SEGMENT});
} else if (cr > 0) {
return ccw({COUNTER_CLOCKWISE});
} else {
return ccw({CLOCKWISE});
}
}
} // namespace haar_lib
#line 5 "Mylib/Geometry/Float/intersect_segments.cpp"
namespace haar_lib {
namespace intersect_segments_impl {
enum status_t { INTERSECTED,
OVERLAPPED,
NOT_INTERSECTED,
SAME };
template <typename T>
struct result {
status_t status;
std::vector<point<T>> crosspoints;
bool is_intersected() const { return status == status_t::INTERSECTED; }
bool is_overlapped() const { return status == status_t::OVERLAPPED; }
bool is_not_intersected() const { return status == status_t::NOT_INTERSECTED; }
bool is_same() const { return status == status_t::SAME; }
};
} // namespace intersect_segments_impl
template <typename T>
auto intersect_segments(const segment<T> &a, const segment<T> &b) {
using namespace intersect_segments_impl;
const T cr = cross(a, b);
if (abs(cr) == 0) { // parallel
if (check_ccw(a.from, a.to, b.from).value * check_ccw(a.from, a.to, b.to).value <= 0 and
check_ccw(b.from, b.to, a.from).value * check_ccw(b.from, b.to, a.to).value <= 0) {
return result<T>({status_t::OVERLAPPED, {}});
} else {
return result<T>({status_t::NOT_INTERSECTED, {}});
}
}
const T t1 = cross(b.from - a.from, diff(b)) / cr;
const T t2 = cross(b.from - a.from, diff(a)) / cr;
if (t1 < 0 or t1 > 1 or t2 < 0 or t2 > 1) { // no crosspoint
return result<T>({status_t::NOT_INTERSECTED, {}});
}
return result<T>({status_t::INTERSECTED, {a.from + diff(a) * t1}});
}
} // namespace haar_lib
#line 3 "Mylib/Graph/Coloring/chromatic_number.cpp"
#include <cstdint>
#line 3 "Mylib/Number/Mod/mod_pow.cpp"
namespace haar_lib {
constexpr int64_t mod_pow(int64_t n, int64_t p, int64_t m) {
int64_t ret = 1;
while (p > 0) {
if (p & 1) (ret *= n) %= m;
(n *= n) %= m;
p >>= 1;
}
return ret;
}
} // namespace haar_lib
#line 6 "Mylib/Graph/Coloring/chromatic_number.cpp"
namespace haar_lib {
int chromatic_number(const std::vector<std::vector<int>> &graph) {
static constexpr int mod = 1000000007;
const int N = graph.size();
std::vector<int> g(N);
for (int i = 0; i < N; ++i) {
for (auto j : graph[i]) {
g[i] |= (1 << j);
}
}
std::vector<int64_t> I(1 << N);
I[0] = 1;
for (int i = 1; i < (1 << N); ++i) {
int c = __builtin_ctz(i);
I[i] = I[i - (1 << c)] + I[(i - (1 << c)) & (~g[c])];
if (I[i] >= mod) I[i] -= mod;
}
const auto check =
[&](int k) {
int64_t t = 0;
for (int i = 0; i < (1 << N); ++i) {
if (__builtin_popcount(i) % 2 == 1)
t -= mod_pow(I[i], k, mod);
else
t += mod_pow(I[i], k, mod);
if (t < 0) t += mod;
if (t >= mod) t -= mod;
}
return (t % mod != 0);
};
int lb = 0, ub = N;
while (std::abs(lb - ub) > 1) {
const auto mid = (lb + ub) / 2;
if (check(mid)) {
ub = mid;
} else {
lb = mid;
}
}
return ub;
}
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples_with_index.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples_with_index.cpp"
#include <tuple>
#include <utility>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples_with_index.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuplesWithIndex {
struct iter {
using value_type = std::tuple<int, Args...>;
value_type value;
bool fetched = false;
int N;
int c = 0;
value_type operator*() {
if (not fetched) {
std::tuple<Args...> temp;
std::cin >> temp;
value = std::tuple_cat(std::make_tuple(c), temp);
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuplesWithIndex(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples_with_index(int N) {
return InputTuplesWithIndex<Args...>(N);
}
} // namespace haar_lib
#line 4 "Mylib/IO/input_vector.cpp"
namespace haar_lib {
template <typename T>
std::vector<T> input_vector(int N) {
std::vector<T> ret(N);
for (int i = 0; i < N; ++i) std::cin >> ret[i];
return ret;
}
template <typename T>
std::vector<std::vector<T>> input_vector(int N, int M) {
std::vector<std::vector<T>> ret(N);
for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
return ret;
}
} // namespace haar_lib
#line 11 "test/aoj/2136/main.test.cpp"
namespace hl = haar_lib;
static constexpr double eps = 1e-7;
using D = hl::double_eps<double, eps>;
bool intersect(const std::vector<hl::point<D>> &a, const std::vector<hl::point<D>> &b) {
for (int i = 0; i < (int) a.size() - 1; ++i) {
for (int j = 0; j < (int) b.size() - 1; ++j) {
auto l1 = hl::line<D>(a[i], a[i + 1]);
auto l2 = hl::line<D>(b[j], b[j + 1]);
if (not hl::intersect_segments(l1, l2).is_not_intersected()) {
return true;
}
}
}
return false;
}
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int N;
while (std::cin >> N, N) {
std::vector<std::vector<hl::point<D>>> lines(N);
for (auto [i, S] : hl::input_tuples_with_index<int>(N)) {
lines[i] = hl::input_vector<hl::point<D>>(S);
}
std::vector<std::vector<int>> graph(N);
for (int i = 0; i < N; ++i) {
for (int j = 0; j < i; ++j) {
if (intersect(lines[i], lines[j])) {
graph[j].push_back(i);
graph[i].push_back(j);
}
}
}
int ans = hl::chromatic_number(graph);
std::cout << ans << std::endl;
}
return 0;
}
test/aoj/2136/main.test.cpp
Floating point number with eps
(Mylib/Geometry/Float/double_eps.cpp)