当前位置：首页 > news >正文

打卡信奥刷题（2684）用C++实现信奥题 P2994 [USACO10OCT] Dinner Time S

news 2026/4/6 7:48:39

P2994 [USACO10OCT] Dinner Time S

题目描述

农场主约翰的N NN（1 ≤ N ≤ 10 3 1 \le N \le 10 ^ 31≤N≤103）头奶牛被编号为1 ∼ N 1 \sim N1∼N，它们正在保加利亚参加 IOI。奶牛们喜欢保加利亚的太阳并享受着它们的假日，一切看起来都没问题。

变化发生在晚餐时间前后。这家餐馆很小，只有M MM（1 ≤ M ≤ N 1 \le M \le N1≤M≤N）个座位，编号为1 ∼ M 1 \sim M1∼M。每头牛从一个位置C X i CX_iCXi，C Y i CY_iCYi进入餐馆（− 10 6 ≤ C X i ≤ 10 6 , − 10 6 ≤ C Y i ≤ 10 6 -10 ^ 6 \le CX_i \le 10 ^ 6,-10 ^ 6 \le CY_i \le 10 ^ 6−106≤CXi≤106,−106≤CYi≤106）；座位可以在S X j SX_jSXj，S Y j SY_jSYj找到（− 10 6 ≤ S X j ≤ 10 6 , − 10 6 ≤ S Y j ≤ 10 6 -10 ^ 6 \le SX_j \le10 ^ 6,-10 ^ 6\le SY_j\le 10 ^ 6−106≤SXj≤106,−106≤SYj≤106）。

奶牛有一种非常有效的（尽管很原始）方法把自己分配到座位上。一旦某只奶牛确定她会先到某个座位上，她就会尽快赶到那里（所有的奶牛都跑得一样快）。

农场主约翰的奶牛和所有获奖的奶牛一样，跳过座位、桌子或其他奶牛都没有问题，因此它们可以直线奔跑。当多头牛可以同时到达一个座位时，最老的牛（在输入数据中出现得更早的牛）获得座位。当一头牛可以第一个到达多个座位时，她也会选择在输入中最早出现的座位。

一些奶牛将不能吃晚饭，这些吃不到饭的饥饿的奶牛正集体计划偷农场主约翰自己的食物。农场主约翰想要一份他应该提防的奶牛名单。（如果没有饥饿的奶牛，则输出0 00）。你能帮他吗？

注：在计算中可能会有超过32 3232位整数范围但在64 6464位整数范围内的数。

输入格式

第一行：两个空格分隔的整数：N NN和M MM。

第2 ∼ N + 1 2 \sim N + 12∼N+1行：第i + 1 i+1i+1行包含两个空格分隔的整数：C X i CX_iCXi和C Y i CY_iCYi。

第N + 2 ∼ N + M + 1 N+2 \sim N+M+1N+2∼N+M+1行：行j + N + 1 j+N+1j+N+1包含两个空格分隔的整数：S X j SX_jSXj和S Y j SY_jSYj。

输出格式

第1 11行到第( N − M ) (N-M)(N−M)行：第i ii行包含农场主约翰应该提防的第i ii头牛的编号。奶牛的编号应递增排序。

输入输出样例 #1

输入 #1

2 1 0 1 1 0 1 10

输出 #1

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1000+5;//为了方便定义数组，直接把数据范围控制好longlonga[maxn],b[maxn],c,d;//a,b表示奶牛计入房间位置，c,d表示座位位置intflag[maxn];//用来标记那些奶牛已经有座位了intpos;//记录有座位的奶牛编号intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i]>>b[i];for(intj=1;j<=m;j++){cin>>c>>d;longlongdis=0;longlongmindis=1e15;for(inti=1;i<=n;i++){if(flag[i]==1)continue;//已有座位，直接跳过dis=(a[i]-c)*(a[i]-c)+(b[i]-d)*(b[i]-d);//计算距离，用勾股定理if(dis<mindis){mindis=dis;//重新赋最小值pos=i;//标记}}flag[pos]=1;//标记，已有座位}if(n==m){cout<<0;return0;}for(inti=1;i<=n;i++){if(flag[i])continue;cout<<i<<endl;}return0;}