• 题面描述
    • 多边形相邻边垂直，边长为整数，边平行坐标轴。要在多边形的点上放一些激光发射器和接收器。满足下列要求：
      • 发射器和接收器不能放置在同一点
      • 发射器发出激光可以沿壁反射，最终到达一个接收器
      • 发射器只能沿角平分线发射激光
    • 求：最多可放置多少对发射器和接收器？点数\(4\leq n\leq 10^5\)
  • 输入格式
    • 第一行给出一个数字\(N\),代表有多少个点. 下面\(N\)行,用来描述点的坐标.其值在\([-10^6,10^6]\)
  • 输出格式
    • 最多可放置多少对发射器和接收器
  • 题解
    • 由光的可逆性，一个拐点若能与其他拐点匹配，必然只存在唯一的拐点与其匹配
    • 由光线沿对角线传播，必存在相应匹配点
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int main(){
    scanf("%d",&n);
    printf("%d\n",n/2);
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄