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 |
|
|
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 |