Div. 2, based on Technocup 2019 Elimination Round 4)"/>
Codeforces Round #528 (Div. 2, based on Technocup 2019 Elimination Round 4)
题目链接:
题意:给你三个点,然你联通这三个点(任意起点),要求使经过的点的个数最少,输出一共经过几个点,和经过的点(经过点的顺序不做要求)。
思路:按x坐标从小到大排序,先从中间点开始存入从上到下经过的点,然后依次存入左右两侧经过的点即可。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
bool f[1111][1111], best[1111][1111];
pair<int,int> p[3];
int main()
{for(int i = 0; i < 3; i++) cin >> p[i].x >> p[i].y;sort(p, p+3);set< pair<int,int> > s;//存入从上到下的路径for(int i = min(min(p[0].y,p[1].y),p[2].y); i <= max(max(p[0].y,p[1].y),p[2].y); i++) s.insert({p[1].x,i});for(int i = p[0].x; i <= p[1].x; i++) s.insert({i,p[0].y}); //存入左侧到中间的路径for(int i = p[1].x; i <= p[2].x; i++) s.insert({i,p[2].y}); //存入中间到右侧的路径cout << s.size() << '\n';for(auto x:s) cout << x.x << ' ' << x.y << '\n';
}
更多推荐
Codeforces Round #528 (Div. 2, based on Technocup 2019 Elimination Round 4)
发布评论