#397465 (C++17) No.947 ABC包囲網

提出ソース

結果

問題	No.947 ABC包囲網
ユーザー	mai
提出日時	2019-11-11 01:03:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	817 ms / 2,000 ms
コード長	7,684 bytes
コンパイル時間	2,778 ms
コンパイル使用メモリ	219,232 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-23 12:11:33
合計ジャッジ時間	22,159 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	2 ms 5,376 KB
testcase_08	AC	2 ms 5,376 KB
testcase_09	AC	2 ms 5,376 KB
testcase_10	AC	2 ms 5,376 KB
testcase_11	AC	2 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	5 ms 5,376 KB
testcase_16	AC	3 ms 5,376 KB
testcase_17	AC	3 ms 5,376 KB
testcase_18	AC	4 ms 5,376 KB
testcase_19	AC	4 ms 5,376 KB
testcase_20	AC	4 ms 5,376 KB
testcase_21	AC	5 ms 5,376 KB
testcase_22	AC	4 ms 5,376 KB
testcase_23	AC	4 ms 5,376 KB
testcase_24	AC	5 ms 5,376 KB
testcase_25	AC	4 ms 5,376 KB
testcase_26	AC	4 ms 5,376 KB
testcase_27	AC	4 ms 5,376 KB
testcase_28	AC	351 ms 5,376 KB
testcase_29	AC	817 ms 5,376 KB
testcase_30	AC	388 ms 5,376 KB
testcase_31	AC	816 ms 5,376 KB
testcase_32	AC	810 ms 5,376 KB
testcase_33	AC	801 ms 5,376 KB
testcase_34	AC	807 ms 5,376 KB
testcase_35	AC	811 ms 5,376 KB
testcase_36	AC	809 ms 5,376 KB
testcase_37	AC	808 ms 5,376 KB
testcase_38	AC	816 ms 5,376 KB
testcase_39	AC	801 ms 5,376 KB
testcase_40	AC	798 ms 5,376 KB
testcase_41	AC	812 ms 5,376 KB
testcase_42	AC	798 ms 5,376 KB
testcase_43	AC	804 ms 5,376 KB
testcase_44	AC	809 ms 5,376 KB
testcase_45	AC	800 ms 5,376 KB
testcase_46	AC	803 ms 5,376 KB
testcase_47	AC	810 ms 5,376 KB
testcase_48	AC	809 ms 5,376 KB
testcase_49	AC	799 ms 5,376 KB
testcase_50	AC	813 ms 5,376 KB
testcase_51	AC	2 ms 5,376 KB
testcase_52	AC	2 ms 5,376 KB
testcase_53	AC	2 ms 5,376 KB
testcase_54	AC	2 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	2 ms 5,376 KB
testcase_57	AC	5 ms 5,376 KB
testcase_58	AC	5 ms 5,376 KB
testcase_59	AC	5 ms 5,376 KB

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

ソースコード

raw source code

#pragma GCC optimize ("O3")
#include "bits/stdc++.h"

using namespace std;
using ll = long long int;

#define debugos cout
#define debug(v) {printf("L%d %s > ",__LINE__,#v);debugos<<(v)<<endl;}
#define debugv(v) {printf("L%d %s > ",__LINE__,#v);for(auto e:(v)){debugos<<e<<" ";}debugos<<endl;}
#define debuga(m,w) {printf("L%d %s > ",__LINE__,#m);for(int x=0;x<(w);x++){debugos<<(m)[x]<<" ";}debugos<<endl;}
#define debugaa(m,h,w) {printf("L%d %s >\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){debugos<<(m)[y][x]<<" ";}debugos<<endl;}}
#define all(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(auto cnt=remove_reference<decltype(l)>::type();(cnt)<(l);++(cnt))
#define rrepeat(cnt,l) for(auto cnt=(l)-1;0<=(cnt);--(cnt))
#define iterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);++(cnt))
#define diterate(cnt,b,e) for(auto cnt=(b);(cnt)!=(e);--(cnt))
const ll MD = 1000000007ll; const long double PI = 3.1415926535897932384626433832795L;
inline void assert_call(bool assertion, function<void()> f) { if (!assertion) { cerr << "assertion fault:" << endl; f(); abort(); } }
template<typename T1, typename T2> inline ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << '(' << p.first << ':' << p.second << ')'; return o; }
template<typename Vec> inline ostream& _ostream_vecprint(ostream& os, const Vec& a) {
  os << '['; for (const auto& e : a) os << ' ' << e << ' '; os << ']'; return os; }
template<typename T> inline ostream& operator<<(ostream& o, const vector<T>& v) { return _ostream_vecprint(o, v); }
template<typename T, size_t S> inline ostream& operator<<(ostream& o, const array<T, S>& v) { return _ostream_vecprint(o, v); }
template<typename T> inline T& chmax(T& to, const T& val) { return to = max(to, val); }
template<typename T> inline T& chmin(T& to, const T& val) { return to = min(to, val); }
void bye(string s, int code = 0) { cout << s << endl; exit(code); }
mt19937_64 randdev(8901016);
template<typename T, typename Random = decltype(randdev), typename enable_if<is_integral<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_int_distribution<T>(l, h)(rand); }
template<typename T, typename Random = decltype(randdev), typename enable_if<is_floating_point<T>::value>::type* = nullptr>
inline T rand(T l, T h, Random& rand = randdev) { return uniform_real_distribution<T>(l, h)(rand); }

#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
#define isvisiblechar(c) (0x21<=(c)&&(c)<=0x7E)
class MaiScanner {
  FILE* fp_;
public:
  inline MaiScanner(FILE* fp):fp_(fp){}
  template<typename T> void input_integer(T& var) noexcept {
    var = 0; T sign = 1;
    int cc = getc_x(fp_);
    for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
      if (cc == '-') sign = -1;
    for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
      var = (var << 3) + (var << 1) + cc - '0';
    var = var * sign;
  }
  inline int c() noexcept { return getc_x(fp_); }
  inline MaiScanner& operator>>(int& var) noexcept { input_integer<int>(var); return *this; }
  inline MaiScanner& operator>>(long long& var) noexcept { input_integer<long long>(var); return *this; }
  inline MaiScanner& operator>>(string& var) {
    int cc = getc_x(fp_);
    for (; !isvisiblechar(cc); cc = getc_x(fp_));
    for (; isvisiblechar(cc); cc = getc_x(fp_))
      var.push_back(cc);
    return *this;
  }
  template<typename IT> inline void in(IT begin, IT end) { for (auto it = begin; it != end; ++it) *this >> *it; }
};
class MaiPrinter {
  FILE* fp_;
public:
  inline MaiPrinter(FILE* fp):fp_(fp){}
  template<typename T>
  void output_integer(T var) noexcept {
    if (var == 0) { putc_x('0', fp_); return; }
    if (var < 0)
      putc_x('-', fp_),
      var = -var;
    char stack[32]; int stack_p = 0;
    while (var)
      stack[stack_p++] = '0' + (var % 10),
      var /= 10;
    while (stack_p)
      putc_x(stack[--stack_p], fp_);
  }
  inline MaiPrinter& operator<<(char c) noexcept { putc_x(c, fp_); return *this; }
  inline MaiPrinter& operator<<(int var) noexcept { output_integer<int>(var); return *this; }
  inline MaiPrinter& operator<<(long long var) noexcept { output_integer<long long>(var); return *this; }
  inline MaiPrinter& operator<<(char* str_p) noexcept { while (*str_p) putc_x(*(str_p++), fp_); return *this; }
  inline MaiPrinter& operator<<(const string& str) {
    const char* p = str.c_str();
    const char* l = p + str.size();
    while (p < l) putc_x(*p++, fp_);
    return *this;
  }
  template<typename IT> void join(IT begin, IT end, char sep = ' ') { for (bool b = 0; begin != end; ++begin, b = 1) b ? *this << sep << *begin : *this << *begin; }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);


struct Rational{
  ll num, den;
  inline void fix() {
    if (den == 0)
      num = (0 < num) - (0 > num);
    else {
      auto g = gcd(num, den);
      num /= g;
      den /= g;
      if (den < 0) {
        den *= -1;
        num *= -1;
      }
    }
  }
  
  inline bool operator==(const Rational& r) const noexcept {
    return den == 0 && r.den == 0 ? num == r.num : num*r.den == r.num*den;
  }
  inline bool operator<(const Rational& r) const noexcept {
    return den == 0 && r.den == 0 ? num < r.num : num*r.den < r.num*den;
  }
  inline bool operator>(const Rational& r) const noexcept {
    return den == 0 && r.den == 0 ? num > r.num : num*r.den > r.num*den;
  }
  inline Rational(ll n=0, ll d=1) : num(n), den(d) { fix(); }
};
inline ostream& operator <<(ostream &o, Rational p) { o << p.num << '/' << p.den ; return o; }




using Angle = pair<int8_t, Rational>; // 3,4象限ならfirst&1 = 1, second = tangent
inline Angle ataan(ll y, ll x) {
  return pair<int8_t, Rational>{x < 0, Rational{y, x}};
}

// 180度回転させる。
// a.first ^= 1 だけで十分だが、これだけでは
// ある角度に対してAngleが唯一にならなくなる
// 0度と180度は angle.first&1 == 0の時のみに存在するため
inline Angle inverse(Angle a) {
  if (a.second.den == 0)
    a.second.num *= -1;
  else
    a.first ^= 1;
  return a;
}

inline void fix(Angle& a, Angle& b) {
  a.first &= 1;
  b.first &= 1;
  if (a.first == b.first) { // R180を超えない
    if (a.second > b.second) swap(a, b);
  }
  else {
    if (a.second < b.second) swap(a, b);
    if (a.first > b.first) b.first += 2;
  }
}

//

int N;
Angle angles[10101];

//


int main() {
  
  scanner >> N;
  repeat(i, N) {
    int x, y;
    scanner >> x >> y;
    angles[i] = ataan(y, x); // 角度情報として保持
  }
  
  sort(angles, angles+N);
  
  // 実装を楽にするため、二週にしておく
  repeat(i, N) {
    angles[i+N] = angles[i];
    angles[i+N].first += 2;
  }
  
  // debuga(angles, N*2);
  
  ll ans = 0;
  repeat(i, N-1) {
    auto ai = angles[i];
    iterate(j, i+1, N) {
      auto aj = angles[j];
      
      // 角度が同じ <=> 直線状に並んでいる <=> 面積が0 => 省略する
      if (ai.second == aj.second) continue;
      if (ai.second.den == 0 && aj.second.den == 0) continue;
      
      // この角度の範囲の頂点を選べば、原点が内部に入る三角形になる
      // -> ai+180 から aj+180 まで
      auto abe = inverse(ai);
      auto aen = inverse(aj);
      // 間違った弧を取ってしまうことがあるので修正
      fix(abe, aen);
      auto ibe = upper_bound(angles, angles+N*2, abe);
      auto ien = lower_bound(angles, angles+N*2, aen);
      ans += distance(ibe, ien);
    }
  }
  
  cout << ans/3 << endl;
  
  return 0;
}

yukicoder

結果

テストケース

ソースコード