fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define dbg(x) cout << #x << " = " << x << endl;
  3. #define print_v(x) cout << #x << "[]: "; for (auto e : x) cout << e << " "; cout << '\n';
  4. #define RAYA cout << string(10, '=') << '\n';
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
  9. template<class T>
  10.  
  11. struct Point {
  12.     typedef Point P;
  13.     double x, y;
  14.     explicit Point(T x = 0, T y = 0) : x(x), y(y) {}
  15.     bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
  16.     bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
  17.     P operator+(P other) const { return P(x + other.x, y + other.y); }
  18.     P operator-(P other) const { return P(x - other.x, y - other.y); }
  19.     P operator*(T c) const { return P(x * c, y * c); }
  20.     P operator/(T c) const { return P(x/c, y/c); }
  21.     //friend T operator*(T c, const P p) { return p * c; }
  22.     T operator*(P other) const { return x * other.x + y * other.y; }
  23.     T operator^(P other) const { return x * other.y - y * other.x; }
  24.     T dot(P other) const { return (*this) * other; }
  25.     T cross(P other) const { return (*this) ^ other; }
  26.     T cross(P a, P b) const { return (a - *this).cross(b - *this); }
  27.     T dist2() const { return x * x + y * y; }
  28.     double norm() const { return sqrt((double) dist2()); }
  29.     friend double dist(P p, P q) { return (p - q).norm(); }
  30.     double angle() const { return atan2(y, x); }
  31.     P unit() const { return *this/norm(); }
  32.     P perp() const { return P(-y, x); }
  33.     P normal() const { return perp().unit(); }
  34.     P rotate(double a) const {
  35.         return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
  36.     }
  37.     P rotate(Point other, double a) const {
  38.         return (*this - other).rotate(a) + other;
  39.     }
  40.     friend istream& operator>>(istream& is, P& other) {
  41.         return is >> other.x >> other.y;
  42.     }
  43.     friend ostream& operator<<(ostream& os, P other) {
  44.         return os << "(" << other.x << "," << other.y << ")";
  45.     }
  46. };
  47.  
  48. template<class P>
  49. pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
  50. 	auto d = (e1 - s1).cross(e2 - s2);
  51. 	if (d == 0) // if parallel
  52. 		return {-(s1.cross(e1, s2) == 0), P(0, 0)};
  53. 	auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
  54. 	return {1, (s1 * p + e1 * q) / d};
  55. }
  56.  
  57. int main() {
  58.     int R,B;
  59.     cin >> R >> B;
  60.     if (R != B) {
  61.         cout << "No\n";
  62.         return 0;
  63.     }
  64.     int n = R;
  65.     vector<Point<double>> a(n), b(n);
  66.     for (auto &e : a) cin >> e;
  67.     for (auto &e : b) cin >> e;
  68.  
  69.     vector<int> idx(n);
  70.     iota(idx.begin(), idx.end(), 0);
  71.     do {
  72.         bool ok = true;
  73.         for (int i = 0; i < n - 1; i++) {
  74.             for (int j = i + 1; j < n; j++) {
  75.                 pair<int, Point<double>> t = lineInter(a[i], b[idx[i]], a[j], b[idx[j]]); 
  76.                 if (t.first == 0) continue;
  77.                 Point<double> tt = t.second;
  78.                 if (tt.x <= max(a[i].x, b[idx[i]].x) and tt.x >= min(a[i].x, b[idx[i]].x) and tt.x <= max(a[j].x, b[idx[j]].x) and tt.x >= min(a[j].x, b[idx[j]].x)) {
  79.                     ok = false;
  80.                     break;
  81.                 }
  82.             }
  83.         }
  84.         if (ok) {
  85.             cout << "Yes\n";
  86.             return 0;
  87.         }
  88.     } while(next_permutation(idx.begin(), idx.end()));
  89.     cout << "No\n";
  90.     return 0;
  91. }
  92.  
  93.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
2 1
1 0
2 2
3 1
stdout
copy 
No
https://ideone.com/oDnHOU
language:
C++14 (clang 8.0)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!