Submission #541664

#	Time	Username	Problem	Language	Result	Execution time	Memory
541664		colazcy	Paralelogrami (COCI17_paralelogrami)	C++17	56 / 140	1 ms	340 KiB

paralelogrami

#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <tuple>
#include <algorithm>
#include <random>
#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;
	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){
	// debug("(%d,%d) (%d,%d) (%d,%d)\n",a.x,a.y,b.x,b.y,c.x,c.y);
	// debug("%d\n",(b - a) * (c - a));
	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){
	// assert(chk(p[a],p[b],p[c]));
	ans.emplace_back(a,b,c);
	assert(ans.size() <= 2500);
	p[c] = nxt(p[a],p[b],p[c]);
}

std::mt19937 eng(123);
int suf[maxn];
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;
	}
	rep(i,1,n)suf[i] = i;
	std::shuffle(suf + 1,suf + 1 + n,eng);
	int perm[] = {-1,-1,-1,-1};
	[&perm](){
		rep(i,1,n)
			rep(j,i + 1,n)
				rep(k,j + 1,n)
					if(chk(p[suf[i]],p[suf[j]],p[suf[k]])){
						perm[1] = suf[i];
						perm[2] = suf[j];
						perm[3] = suf[k];
						return;
				}
	}();
	if(perm[1] == -1){
		std::puts("-1");
		return 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;
	};
	
	int tot = 0,tar = -1,trans[33];

	rep(i,1,3)
		rep(j,i + 1,3)
			seq[++tot] = p[perm[i]] - p[perm[j]],
			seq[++tot] = p[perm[j]] - p[perm[i]];
	[&trans,&tar,&tot](){
		rep(i,1,tot)trans[i] = i;
		do{
			Point now{0,0};
			rep(i,1,tot){
				now = now + seq[trans[i]];
				if(now.x > 0 && now.y > 0){
					// debug("x : %d\n",trans[1]);
					// debug("v : (%d,%d)\n",now.x,now.y);
					tar = i;
					return;
				}
				
			}
		}while(std::next_permutation(trans + 1,trans + 1 + tot));
	}();

	assert(tar != -1);
	// debug("tar = %d\n",tar);
	
	// debug("(%d,%d)\n",seq[trans[1]].x,seq[trans[1]].y);
	while(true){
		// 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);
		if(p[perm[1]].x >= 20 && p[perm[1]].y >= 20 && p[perm[2]].x >= 20 && p[perm[2]].y >= 20 && p[perm[3]].x >= 20 && p[perm[3]].y >= 20)break;

		rep(id,1,tar){
			let v = seq[trans[id]];
			[&](){
				rep(i,1,3)
					rep(j,1,3)
						if(i != j && (p[perm[j]] - p[perm[i]]) == v){
							move_vec(i,j,other(i,j));
							return;
						}
			}();
		}
	}

	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 (stderr)

paralelogrami.cpp: In function 'int main()':
paralelogrami.cpp:51:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
paralelogrami.cpp:52:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14