题目链接
102576G
题解
题意
n 个桌子，n个房间，分别连接桌子和房子，保证n条路线之间没有交叉。 求n条路线。
思路
将点按照横坐标排序，两两配对，记录最高点，最低点和最左端。
将配对好的点画圈连接，每个圈有六个点，保证该圈的最高点高于之前的最高点，最低点低于之前的最低点，最左端左于之前的最左端。
转圈圈~~
AC代码
#include <bits/stdc++.h>
using namespace std
;
#define INF (0x3f3f3f3f)
int T
;
int n
;
int const N
= 10;
struct Point
{
int x
, y
;
Point() : x(), y() {
}
bool operator<(const Point
&a
) const {
if (x
== a
.x
) return y
> a
.y
;
return x
< a
.x
;
}
} ta
[N
], ro
[N
];
int le
, up
, bot
;
int main() {
ios
::sync_with_stdio(false);
cin
.tie(nullptr);
cout
.tie(nullptr);
cin
>> T
;
while (T
--) {
up
= -INF
;
le
= bot
= INF
;
cin
>> n
;
for (int i
= 1; i
<= n
; i
++) { cin
>> ta
[i
].x
>> ta
[i
].y
; up
= max(ta
[i
].y
, up
); bot
= min(ta
[i
].y
, bot
);}
for (int i
= 1; i
<= n
; i
++) { cin
>> ro
[i
].x
>> ro
[i
].y
; up
= max(ro
[i
].y
, up
); bot
= min(ro
[i
].y
, bot
);}
sort(ta
+ 1, ta
+ 1 + n
);
sort(ro
+ 1, ro
+ 1 + n
);
le
= min(ro
[1].x
, ta
[1].x
);
for (int i
= 1; i
<= n
; i
++) {
le
-= 1, up
+= 1, bot
-= 1;
cout
<< 6 << '\n';
cout
<< ta
[i
].x
<< ' ' << ta
[i
].y
<< '\n';
cout
<< ta
[i
].x
<< ' ' << up
<< '\n';
cout
<< le
<< ' ' << up
<< '\n';
cout
<< le
<< ' ' << bot
<< '\n';
cout
<< ro
[i
].x
<< ' ' << bot
<< '\n';
cout
<< ro
[i
].x
<< ' ' << ro
[i
].y
<< '\n';
}
}
return 0;
}
后记
一定要仔细读题！
做这道题时少读了一句导致漏掉了关键条件——点不在一条直线上QAQ！
我的锅！
