#528805 (C++17) No.1144 Triangles

提出ソース

結果

問題	No.1144 Triangles
ユーザー	SHIJOU
提出日時	2020-08-12 18:51:20
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	460 ms / 3,000 ms
コード長	6,964 bytes
コンパイル時間	2,646 ms
コンパイル使用メモリ	210,500 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-04-18 00:49:11
合計ジャッジ時間	9,066 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	1 ms 6,944 KB
testcase_04	AC	460 ms 6,940 KB
testcase_05	AC	459 ms 6,940 KB
testcase_06	AC	457 ms 6,940 KB
testcase_07	AC	448 ms 6,944 KB
testcase_08	AC	452 ms 6,944 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	1 ms 6,940 KB
testcase_11	AC	1 ms 6,940 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	419 ms 6,944 KB
testcase_15	AC	407 ms 6,944 KB
testcase_16	AC	434 ms 6,940 KB
testcase_17	AC	436 ms 6,940 KB
testcase_18	AC	439 ms 6,940 KB
testcase_19	AC	22 ms 6,944 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	3 ms 6,944 KB
testcase_22	AC	416 ms 6,944 KB
testcase_23	AC	25 ms 6,940 KB
testcase_24	AC	417 ms 6,940 KB
testcase_25	AC	138 ms 6,944 KB
testcase_26	AC	16 ms 6,940 KB
testcase_27	AC	10 ms 6,944 KB
testcase_28	AC	83 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const double EPS = 1e-10;
double add(double a, double b) {
  if(abs(a+b) < EPS*(abs(a)+abs(b))) return 0;
  return a+b;
}
struct Vector {
  double x, y;
  Vector(double x=0, double y=0):x(x), y(y) {}
  Vector const operator-() const {return Vector(-x, -y);}
  Vector operator+(Vector v) {return Vector(add(x, v.x), add(y, v.y));}
  Vector operator-(Vector v) {return Vector(add(x, -v.x), add(y, -v.y));}
  Vector operator*(double d) {return Vector(x*d, y*d);}
  Vector operator/(double d) {return Vector(x/d, y/d);}
  bool const operator!=(const Vector v) const {return abs(x-v.x)>EPS or abs(y-v.y)>EPS;}
  double dot(Vector v) {return add(x*v.x, y*v.y);}
  double cross(Vector v) {return add(x*v.y, -y*v.x);}
  Vector rotate(double theta) {return Vector(add(x*cos(theta), -y*sin(theta)), add(x*sin(theta), y*cos(theta)));}
};
bool comps(Vector &a, Vector &b) {
  return a.cross(b) > 0;
}
const Vector origin = Vector(0, 0);
struct Circle {
  Vector c;
  double r;
  Circle(Vector c=Vector(), double r=0):c(c), r(r) {}
};
istream &operator>>(istream &is, Vector &v) {return is >> v.x >> v.y;}
ostream &operator<<(ostream &os, const Vector &v) {return os << v.x << ' ' << v.y;}
istream &operator>>(istream &is, Circle &c) {return is >> c.c >> c.r;}
ostream &operator<<(ostream &os, const Circle &c) {return os << c.c << ' ' << c.r;}
double sqdist(Vector v, Vector u) {return (v-u).dot(v-u);}
//線分v2-v1上にあるか
bool on_seg(Vector &v1,Vector &v2, const Vector &p) {
  return (v1-p).cross(v2-p) == 0 && (v1-p).dot(v2-p) <= 0;
}
//v1-v2とu1-u2の交点
Vector intersection(Vector &v1,Vector &v2,Vector &u1,Vector &u2) {
  assert((v1-v2).cross(u1-u2)); //2直線が平行だとだめ
  return v1 + (v2-v1)*((u2-u1).cross(u1-v1)/(u2-u1).cross(v2-v1));
}
//p2-p1へのQの投影
Vector projection(Vector &p1,Vector &p2,Vector &Q) {
  return p1+(p2-p1)*(Q-p1).dot(p2-p1)/sqdist(p1, p2);
}
//p1-p2を軸としたQの線対称移動
Vector reflection(Vector &p1,Vector &p2,Vector &Q) {
  return projection(p1, p2, Q)*2-Q;
}
//2円が2点で交わりを持つか
bool com_cir(Circle &a, Circle &b) {
  return add((a.r+b.r)*(a.r+b.r), - sqdist(a.c, b.c)) > 0;
}
//円aが円bを真に含んでいるか
bool over_cir(Circle &a, Circle &b) {
  return add(a.r - sqrt(sqdist(a.c, b.c)), -b.r) > 0;
}
//円aが円bを含む&接している
bool intouch_cir(Circle &a, Circle &b) {
  return add(a.r - sqrt(sqdist(a.c, b.c)), -b.r) == 0;
}
//円aが円bを含まない&接している
bool outtouch_cir(Circle &a, Circle &b) {
  return add((a.r+b.r)*(a.r+b.r), - sqdist(a.c, b.c)) == 0;
}
//円aが真に含むか
bool in_cir(Circle &a, Vector &p) {
  return add(sqdist(a.c, p), -a.r*a.r) < 0;
}
//円周上にあるか
bool on_cir(Circle &a, Vector &p) {
  return add(sqdist(a.c, p), -a.r*a.r) == 0;
}
bool cmp_x(const Vector &v, const Vector &u) {
  if(v.x != u.x) return v.x < u.x;
  return v.y < u.y;
}
bool cmp_y(const Vector &v, const Vector &u) {
  if(v.y != u.y) return v.y < u.y;
  return v.x < u.x;
}
//凸包 頂点数nの頂点集合vv
vector<Vector> convex_hull(vector<Vector> &vv, int n) {
  sort(vv.begin(), vv.end(), cmp_x);
  int k = 0;
  vector<Vector> res(n*2);
  for(int i = 0; i < n; i++) {
    while(k > 1 && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
    res[k++] = vv[i];
  }
  for(int i = n-2, t = k; i >= 0; i--) {
    while(k > t && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
    res[k++] = vv[i];
  }
  res.resize(k-1);
  return res;
}
//点と線の距離
double distpl(Vector &p0, Vector &p1, Vector &Q) {
  Vector pp = projection(p0, p1, Q);
  return sqrt(sqdist(pp, Q));
}
//線分と線分の距離
double distss(Vector &p0, Vector &p1, Vector &p2, Vector &p3) {
  if((p0-p1).cross(p2-p3) != 0) {
    Vector p = intersection(p0, p1, p2, p3);
    if(on_seg(p0, p1, p) and on_seg(p2, p3, p)) {
      return 0.0;
    }
  }
  double res = min({sqdist(p0, p2), sqdist(p0, p3), sqdist(p1, p2), sqdist(p1, p3)});
  Vector pp0, pp1, pp2, pp3;
  pp2 = projection(p0, p1, p2);
  pp3 = projection(p0, p1, p3);
  pp0 = projection(p2, p3, p0);
  pp1 = projection(p2, p3, p1);
  if(on_seg(p0, p1, pp2)) res = min(res, sqdist(pp2, p2));
  if(on_seg(p0, p1, pp3)) res = min(res, sqdist(pp3, p3));
  if(on_seg(p2, p3, pp0)) res = min(res, sqdist(pp0, p0));
  if(on_seg(p2, p3, pp1)) res = min(res, sqdist(pp1, p1));
  res = sqrt(res);
  return res;
}

const int mod = 1000000007;
//const int mod = 998244353;

struct mint {
  int64_t x;
  mint(int64_t x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(int64_t t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  //for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

//head

int n;
mint ans;
vector<Vector> xy;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  xy.resize(n);
  rep(i, n) cin >> xy[i];

  rep(i, n) {
    //cout << endl;
    vector<Vector> U;
    rep(j, n) if(xy[i] != xy[j]) {
      Vector t = xy[i]-xy[j];
      if(t.y < 0) t = -t;
      U.emplace_back(t);
    }
    sort(all(U), comps);
    //rep(i, U.size()) cout << U[i] << endl;
    Vector X = origin;
    rep(j, U.size()) {
      ans += ll(X.cross(U[j])+0.1);
      X = X + U[j];
    }
  }

  cout << ans/3 << endl;
}

yukicoder

結果

テストケース

ソースコード