oj.uz

Submission #541651

# Submission time Handle Problem Language Result Execution time Memory
541651 2022-03-24T01:51:37 Z colazcy Paralelogrami (COCI17_paralelogrami) C++17
0 / 140
 1000 ms 212 KB 
#include <cstdio>
#include <cassert>
#include <cctype>
#include <vector>
#include <tuple>
#include <algorithm>
#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;

int read(){
	int x = 0,f = 1; char c = std::getchar();
	while(!std::isdigit(c))f = c == '-' ? -1 : 1,c = std::getchar();
	while(std::isdigit(c))x = x * 10 + c - '0',c = std::getchar();
	return x * f;
}

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};}
	int operator * (const Point &t)const{
		return x * t.y - y * t.x;
	}
	int h()const{
		return (x + 10) * 21 + (y + 10);
	}
}p[maxn];
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};
}
void oper(const int a,const int b,const int c){
	ans.emplace_back(a,b,c);
	assert(ans.size() <= 2500);
	p[c] = nxt(p[a],p[b],p[c]);
}

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);
	
	int a = -1,b = -1,c = -1;
	rep(i,1,n)
		rep(j,i + 1,n)
			rep(k,j + 1,n){
				if(((p[j] - p[i]) * (p[k] - p[i]) == 0) && ((p[k] - p[j]) * (p[i] - p[j]) == 0) && ((p[i] - p[k]) * (p[j] - p[k]) == 0))continue;
				a = i;
				b = j;
				c = k;
			}
	if(a == -1){
		std::puts("-1");
		return 0;
	}
	while(true){
		if(p[a].x >= 20 && p[b].x >= 20 && p[c].x >= 20 && p[a].y >= 20 && p[b].y >= 20 && p[c].y >= 20)break;
		let mix = std::min({p[a].x,p[b].x,p[c].x});
		let miy = std::min({p[a].y,p[b].y,p[c].y});
		{
			let pa = p[a];
			let pb = p[b];
			let pc = nxt(p[a],p[b],p[c]);
			let nmix = std::min({pa.x,pb.x,pc.x});
			let nmiy = std::min({pa.y,pb.y,pc.y});
			if(nmix >= mix && nmiy >= miy && (nmix > mix || nmiy > miy)){
				oper(a,b,c);
				continue;
			}
		}
		{
			let pa = p[a];
			let pb = nxt(p[a],p[c],p[b]);
			let pc = p[c];
			let nmix = std::min({pa.x,pb.x,pc.x});
			let nmiy = std::min({pa.y,pb.y,pc.y});
			if(nmix >= mix && nmiy >= miy && (nmix > mix || nmiy > miy)){
				oper(a,c,b);
				continue;
			}
		}
		{
			let pa = nxt(p[b],p[c],p[a]);
			let pb = p[b];
			let pc = p[c];
			let nmix = std::min({pa.x,pb.x,pc.x});
			let nmiy = std::min({pa.y,pb.y,pc.y});
			if(nmix >= mix && nmiy >= miy && (nmix > mix || nmiy > miy)){
				oper(b,c,a);
				continue;
			}
		}
	}
	rep(i,1,n)
		if(i == a || i == c || i == c)continue;
		else oper(a,b,i);
	
	rep(i,1,n)
		assert(p[i].x >= 0),
		assert(p[i].y >= 0);
	assert(ans.size() <= 2500);
	std::printf("%d",(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:46:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  std::scanf("%d",&n);
      |  ~~~~~~~~~~^~~~~~~~~
paralelogrami.cpp:47:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  rep(i,1,n)std::scanf("%d %d",&p[i].x,&p[i].y);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB selected three points is not collinear
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Integer 8127 violates the range [-1, 2500]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Integer 4122 violates the range [-1, 2500]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Integer 5947 violates the range [-1, 2500]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 212 KB Time limit exceeded
2 Halted 0 ms 0 KB -