Submission #306187


Source Code Expand

#ifdef KOMAKI_LOCAL
#include <omp.h>
#else
#define NDEBUG
#endif

#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64         int64_t
#define rep(i, n)   for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v)       ((i64)((v).size()))
#define bit(n)      (((i64)1)<<((i64)(n)))
#define all(v)      (v).begin(), (v).end()

template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
#define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; }
#define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; }
#define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; }
#define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; }
#define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; }
#define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; }
#define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; }













unordered_map<double, i64> s;
double getIndex(i64 x, i64 y){ return x * 1e10 + y; }
double getIndex(tuple<i64, i64> tup){ return getIndex(get<0>(tup), get<1>(tup)); }
inline void check(vector<tuple<i64, i64>> v)
{
  for(auto tup: v)if(s.count(getIndex(tup)) == 0) return;
  vector<i64> ans;
  //DEBUG1(v);
  for(auto tup: v) ans.push_back(s[getIndex(tup)] +  1);
  sort(all(ans));
  cout << 4 << endl;
  for(auto t: ans) cout << t << endl;
  exit(0);
}

int main()
{
  i64 n;
  cin >> n;
  vector<tuple<i64, i64>> v;
  rep(i, n){
    if(1){
      i64 x, y;
      cin >> x >> y;
      v.push_back(make_tuple(x, y));
      s[getIndex(x, y)] = i;
    }else{
      i64 x = rand() % 10;
      i64 y = rand() % 10;
      v.push_back(make_tuple(x, y));
      s[getIndex(x, y)] = i;
      DEBUG2(x, y);
    }
  }


  rep(i, n)rep(j, i){
    i64 dx = get<0>(v[i]) - get<0>(v[j]);
    i64 dy = get<1>(v[i]) - get<1>(v[j]);
    if(v[i] == v[j]) continue;

    i64 sx[] = {1, 1, -1, -1};
    i64 sy[] = {1, -1, 1, -1};
    //DEBUG2(v[i], v[j]);
    vector<tuple<i64, i64>> v_0;
    vector<tuple<i64, i64>> v_1;
    rep(k, 4){
      tuple<i64, i64> point_0(sx[k] * dy + get<0>(v[i]), sy[k] * dx + get<1>(v[i]));
      if(point_0 == v[j]) continue;
      v_0.push_back(point_0);
    }
    rep(l, 4){
      tuple<i64, i64> point_1(sx[l] * dy + get<0>(v[j]), sy[l] * dx + get<1>(v[j]));
      if(point_1 == v[i]) continue;
      v_1.push_back(point_1);
    }
    for(auto &point_0: v_0)for(auto &point_1: v_1){
        if(get<0>(point_0) - get<0>(point_1) != dx) continue;
        if(get<1>(point_0) - get<1>(point_1) != dy) continue;
        i64 dx_0 = get<0>(v[i]) - get<0>(point_1);
        i64 dy_0 = get<1>(v[i]) - get<1>(point_1);
        i64 dx_1 = get<0>(v[j]) - get<0>(point_0);
        i64 dy_1 = get<1>(v[j]) - get<1>(point_0);
        if(dx_0 * dx_0 + dy_0 * dy_0 != dx_1 * dx_1 + dy_1 * dy_1) continue;
        vector<tuple<i64, i64>> points;
        points.push_back(point_0);
        points.push_back(point_1);
        points.push_back(v[i]);
        points.push_back(v[j]);
        //DEBUG2(l, k);
        //DEBUG1(points);
        check(points);
    }
  }
  cout << 0 << endl;
}














Submission Info

Submission Time
Task C - Regular Polygon
User Komaki
Language C++11 (GCC 4.8.1)
Score 100
Code Size 6201 Byte
Status AC
Exec Time 1555 ms
Memory 932 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 20
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt, subtask1_special05.txt, subtask1_special06.txt, subtask1_special07.txt, subtask1_special08.txt, subtask1_special09.txt, subtask1_special10.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 26 ms 804 KB
subtask0_sample_02.txt AC 25 ms 792 KB
subtask1_random01.txt AC 590 ms 932 KB
subtask1_random02.txt AC 584 ms 796 KB
subtask1_random03.txt AC 571 ms 804 KB
subtask1_random04.txt AC 569 ms 800 KB
subtask1_random05.txt AC 40 ms 924 KB
subtask1_random06.txt AC 45 ms 796 KB
subtask1_random07.txt AC 573 ms 804 KB
subtask1_random08.txt AC 578 ms 796 KB
subtask1_special01.txt AC 26 ms 672 KB
subtask1_special02.txt AC 26 ms 804 KB
subtask1_special03.txt AC 27 ms 800 KB
subtask1_special04.txt AC 26 ms 804 KB
subtask1_special05.txt AC 572 ms 920 KB
subtask1_special06.txt AC 95 ms 928 KB
subtask1_special07.txt AC 45 ms 808 KB
subtask1_special08.txt AC 50 ms 804 KB
subtask1_special09.txt AC 1555 ms 928 KB
subtask1_special10.txt AC 27 ms 916 KB