結果
問題 | No.1144 Triangles |
ユーザー |
![]() |
提出日時 | 2020-07-31 03:07:19 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,588 bytes |
コンパイル時間 | 1,563 ms |
コンパイル使用メモリ | 156,888 KB |
実行使用メモリ | 10,272 KB |
最終ジャッジ日時 | 2024-07-05 06:50:04 |
合計ジャッジ時間 | 12,270 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 TLE * 1 -- * 1 |
ソースコード
/*このコード、と~おれ!Be accepted!∧_∧(。・ω・。)つ━☆・*。⊂ ノ ・゜+.しーJ °。+ *´¨).· ´¸.·*´¨) ¸.·*¨)(¸.·´ (¸.·'* ☆*/#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <vector>#include <numeric>#include <iostream>#include <random>#include <map>#include <unordered_map>#include <queue>#include <regex>#include <functional>#include <complex>#include <list>#include <cassert>#include <iomanip>#include <set>#include <stack>#include <bitset>////多倍長整数, cpp_intで宣言//#include <boost/multiprecision/cpp_int.hpp>//using namespace boost::multiprecision;//#pragma gcc target ("avx2")//#pragma gcc optimization ("O3")//#pragma gcc optimization ("unroll-loops")#define rep(i, n) for(int i = 0; i < (n); ++i)#define printynl(a) printf(a ? "yes\n" : "no\n")#define printyn(a) printf(a ? "Yes\n" : "No\n")#define printYN(a) printf(a ? "YES\n" : "NO\n")#define printim(a) printf(a ? "possible\n" : "imposible\n")#define printdb(a) printf("%.50lf\n", a) //少数出力#define printLdb(a) printf("%.50Lf\n", a) //少数出力#define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ)#define prints(s) printf("%s\n", s.c_str()) //string出力#define all(x) (x).begin(), (x).end()#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)#define Please return#define AC 0#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */#define inf numeric_limits<double>::infinity();#define linf numeric_limits<long double>::infinity()using ll = long long;using ull = unsigned long long;constexpr int INF = 1073741823;constexpr int MINF = -1073741823;constexpr ll LINF = ll(4661686018427387903);constexpr ll MOD = 1e9 + 7;constexpr long double eps = 1e-6;const long double PI = acosl(-1.0L);using namespace std;void scans(string& str) {char c;str = "";scanf("%c", &c);if (c == '\n')scanf("%c", &c);while (c != '\n' && c != -1 && c != ' ') {str += c;scanf("%c", &c);}}void scanc(char& str) {char c;scanf("%c", &c);if (c == -1)return;while (c == '\n') {scanf("%c", &c);}str = c;}double acot(double x) {return PI / 2 - atan(x);}ll LSB(ll n) { return (n & (-n)); }template<typename T>T chmin(T& a, const T& b) {if (a > b)a = b;return a;}template<typename T>T chmax(T& a, const T& b) {if (a < b)a = b;return a;}/*-----------------------------------------ここからコード-----------------------------------------*//** @title modint* @docs kyopro/docs/modint.md*/template<int mod>struct modint {int val, size;vector<ll> fac, inv, facinv;modint() : val(0), size(0) {};modint(ll x) : val(x >= 0 ? x % mod : (mod + x % mod) % mod), size(0) {};//siz <= 1e7 くらいvoid cominit(const int siz) {size = siz;fac.assign(siz + 1, 0);inv.assign(siz + 1, 0);facinv.assign(siz + 1, 0);fac[0] = fac[1] = facinv[0] = facinv[1] = inv[0] = 1;for (ll i = 2; i <= siz; ++i) {fac[i] = fac[i - 1] * i % mod;inv[i] = mod - inv[mod % i] * (mod / i) % mod;facinv[i] = facinv[i - 1] * inv[i] % mod;}}modint& operator=(const modint& x) {val = x.val;return *this;}modint& operator+=(const modint& x) {val += x.val;if (val >= mod)val -= mod;return *this;}modint& operator-=(const modint& x) {val += mod - x.val;if (val >= mod)val -= mod;return *this;}modint& operator*=(const modint& x) {val = (int)((ll)val * (ll)x.val % mod);return *this;}modint& operator/=(const modint& x) {if (x.val <= size) {ll num = x.val;num *= inv[x.val];num %= mod;val = num;return *this;}int a = x.val, b = mod, u = 1, v = 0, t;while (b > 0) {t = a / b;swap(a -= t * b, b);swap(u -= t * v, v);}*this *= modint(u);return *this;}modint operator++() {val = (val + 1 == mod ? 0 : val + 1);return *this;}modint operator--() {val = (val == 0 ? mod - 1 : val - 1);return *this;}modint operator+(const modint& x) const {return (modint(*this) += x);}modint operator-(const modint& x) const {return (modint(*this) -= x);}modint operator*(const modint& x) const {return (modint(*this) *= x);}modint operator/(const modint& x) const {return (modint(*this) /= x);}bool operator==(const modint& x)const {return (val == x.val);}bool operator!=(const modint& x)const {return (val != x.val);}bool operator<(const modint& x)const {return (val < x.val);}bool operator>(const modint& x)const {return (val > x.val);}modint pow(ll n) {modint ret(1), a(val);while (n > 0) {if (n % 2) ret *= a;a *= a;n /= 2;}return ret;}modint comb(const modint& n, const modint& r) {return (n < r or n < 0 or r < 0) ? 0 : ((fac[n] * (facinv[r] * facinv[n - r] % mod)) % mod);}static int getmod() { return mod; };};struct vector2D {ll x, y;vector2D(ll x, ll y) : x(x), y(y) {}vector2D(ll stx, ll sty, ll enx, ll eny) : x(enx - stx), y(eny - sty) {}vector2D() : x(0), y(0) {}vector2D operator+(const vector2D p) { return vector2D(x + p.x, y + p.y); }vector2D operator-(const vector2D p) { return vector2D(x - p.x, y - p.y); }// スカラー倍vector2D operator*(const ll p) { return vector2D(x * p, y * p); }};inline ll vectorproduct(vector2D p, vector2D q) { return p.x * q.y - p.y * q.x; }inline bool comp(const vector2D& a, const vector2D& b) {if (a.x == 0 and a.y == 0)return true;else if (b.x == 0 and b.y == 0)return false;else if (a.x < 0) {if (b.x < 0) {return vectorproduct(a, b) > 0;}else {return false;}}else {if (b.x < 0) {return true;}else {return vectorproduct(a, b) > 0;}}}int main() {int n;scanf("%d", &n);vector<pair<int, int>> p(n);for (auto& [x, y] : p) {scanf("%d%d", &x, &y);x += 10000;y += 10000;}modint<MOD> ans;vector<vector2D> q(n);rep(i, n) {rep(j, n) {if (p[j].second - p[i].second >= 0)q[j].x = p[j].first - p[i].first, q[j].y = p[j].second - p[i].second;else q[j].x = p[i].first - p[j].first, q[j].y = p[i].second - p[j].second;}vector2D r;sort(all(q), comp);for (int j = n - 1; j >= 0; --j) {r = r + q[j];ans += vectorproduct(q[j], r);}}ans /= 3;printf("%d\n", ans.val);Please AC;}