oj.uz

답안 #541680

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
541680 2022-03-24T07:24:51 Z colazcy Paralelogrami (COCI17_paralelogrami) C++17
140 / 140
 4 ms 516 KB 
#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <tuple>
#include <algorithm>
#include <queue>
#include <map>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_lIM = lim,REPN = 1;REPN <= REPN_lIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("line : %d, Function : %s\n",__LINE__,__FUNCTION__)
constexpr int maxn = 433;
 
std::vector<std::tuple<int,int,int>> ans;
int n;
struct Point{
	int x,y;
	bool operator < (const Point &t)const{
		if(x != t.x)return x < t.x;
		return y < t.y;
	}
	Point operator + (const Point &t)const{return Point{x + t.x,y + t.y};}
	Point operator - (const Point &t)const{return Point{x - t.x,y - t.y};}
	bool operator == (const Point &t)const{return x == t.x && y == t.y;}
	int operator * (const Point &t)const{
		return x * t.y - y * t.x;
	}
	int h()const{
		return (x + 10) * 21 + (y + 10);
	}
 
}p[maxn],seq[233];
Point nxt(const Point a,const Point b,const Point c){
	return Point{a.x + b.x - c.x,a.y + b.y - c.y};
}
bool chk(const Point a,const Point b,const Point c){
	return !(((b - a) * (c - a) == 0) && ((a - b) * (c - b) == 0) && ((a - c) * (b - c) == 0));
}
void oper(const int a,const int b,const int c){
	ans.emplace_back(a,b,c);
	p[c] = nxt(p[a],p[b],p[c]);
}
 
std::map<std::tuple<Point,Point,Point>,std::tuple<int,int,int>> mp;
 
int top;
std::vector<std::tuple<int,int,int>> bfs(const int a,const int b,const int c){
	std::vector<std::tuple<int,int,int>> res;
	std::queue<std::tuple<Point,Point,Point,std::tuple<int,int,int>>> q;
	q.emplace(p[a],p[b],p[c],std::make_tuple(0,0,0));
	while(!q.empty()){
		Point pa,pb,pc;
		std::tuple<int,int,int> faz;
		std::tie(pa,pb,pc,faz) = q.front(); q.pop();
		if(pa.x < -20 || pa.y < -20 || pb.x < -20 || pb.y < -20 || pc.x < -20 || pc.y < -20)continue;
		if(pa.x >= 5 && pa.y >= 5 && pb.x >= 5 && pb.y >= 5 && pc.x >= 5 && pc.y >= 5){
			while(faz != std::make_tuple(0,0,0)){
				res.push_back(faz);
				if(faz == std::make_tuple(a,b,c))pc = nxt(pa,pb,pc);
				if(faz == std::make_tuple(a,c,b))pb = nxt(pa,pc,pb);
				if(faz == std::make_tuple(b,c,a))pa = nxt(pb,pc,pa);
				faz = mp[{pa,pb,pc}];
			}
			break;
		}
		if(mp.find({pa,pb,pc}) != mp.end())continue;
		if(mp.find({pa,pc,pb}) != mp.end())continue;
		if(mp.find({pb,pa,pc}) != mp.end())continue;
		if(mp.find({pb,pc,pa}) != mp.end())continue;
		if(mp.find({pc,pa,pb}) != mp.end())continue;
		if(mp.find({pc,pb,pa}) != mp.end())continue;
 
		mp[{pa,pb,pc}] = faz;
		
		q.emplace(pa,pb,nxt(pa,pb,pc),std::make_tuple(a,b,c));
 
		q.emplace(pa,nxt(pa,pc,pb),pc,std::make_tuple(a,c,b));
 
		q.emplace(nxt(pb,pc,pa),pb,pc,std::make_tuple(b,c,a));
	}
	std::reverse(res.begin(),res.end());
	return res;
}
 
int main(){
	// std::freopen("paralelogrami.in","r",stdin);
	// std::freopen("paralelogrami.out","w",stdout);
	std::scanf("%d",&n);
	rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
	bool flg = true;
	rep(i,1,n)
		flg = flg && (p[i].x >= 0 && p[i].y >= 0);
	if(flg){
		std::puts("0");
		return 0;
	}
	int perm[] = {-1,-1,-1,-1};
	[&perm](){
		rep(i,1,n)
			rep(j,i + 1,n)
				rep(k,j + 1,n)
					if(chk(p[i],p[j],p[k])){
						perm[1] = i;
						perm[2] = j;
						perm[3] = k;
						return;
				}
	}();
	if(perm[1] == -1){
		std::puts("-1");
		return 0;
	}
 
	let vec = bfs(perm[1],perm[2],perm[3]);
	// return 0;
	// assert(!vec.empty());
	for(let &p : vec)
		oper(std::get<0>(p),std::get<1>(p),std::get<2>(p));
	// assert(p[perm[1]].x >= 0);
	// assert(p[perm[1]].y >= 0);
	
	let move_vec = [&perm](const int a,const int b,const int c){
		oper(perm[b],perm[c],perm[a]);
		oper(perm[a],perm[b],perm[c]);
	};
 
	let other = [](const int a,const int b){
		if(1 != a && 1 != b)return 1;
		if(2 != a && 2 != b)return 2;
		if(3 != a && 3 != b)return 3;
		return -1;
	};
	// debug("(%d,%d) (%d,%d) (%d,%d)\n",p[perm[1]].x,p[perm[1]].y,p[perm[2]].x,p[perm[2]].y,p[perm[3]].x,p[perm[3]].y);
	let a = perm[1],b = perm[2],c = perm[3];
	rep(i,1,n)
		if(i != a && i != b && i != c){
			if(chk(p[a],p[b],p[i]))oper(a,b,i);
			else if(chk(p[b],p[c],p[i]))oper(b,c,i);
			else if(chk(p[a],p[c],p[i]))oper(a,c,i);
		}
 
	rep(i,1,n)
		assert(p[i].x >= 0),
		assert(p[i].y >= 0);
	std::printf("%d\n",(int)ans.size());
	for(let &t : ans)
		std::printf("%d %d %d\n",std::get<0>(t),std::get<1>(t),std::get<2>(t));
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message

paralelogrami.cpp: In function 'int main()':
paralelogrami.cpp:126:6: warning: variable 'move_vec' set but not used [-Wunused-but-set-variable]
  126 |  let move_vec = [&perm](const int a,const int b,const int c){
      |      ^~~~~~~~
paralelogrami.cpp:131:6: warning: variable 'other' set but not used [-Wunused-but-set-variable]
  131 |  let other = [](const int a,const int b){
      |      ^~~~~
paralelogrami.cpp:92:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
paralelogrami.cpp:93:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |  rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 292 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 292 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #6
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #8
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 4 ms 412 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #9
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 424 KB Output is correct
3 Correct 2 ms 340 KB Output is correct

Subtask #10
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 3 ms 516 KB Output is correct
3 Correct 1 ms 300 KB Output is correct