seuOJ 首页 题库 比赛 评测 排名 讨论 帮助 返回比赛
登录 注册

J. 跑步锻炼管理系统

传统 4000 ms 512 MiB
标准 IO
文本比较
转到题库 提交记录 附加文件 返回比赛

题目描述

这并非一道难题。

我校《学生体育指导手册》指出，一、二年级学生每学期必须进行课外锻炼，以跑步的方式进行。

你需要实现一个简化的跑步锻炼管理系统，判定提交的跑步锻炼记录是否有效，并对其进行统计。

初始时的配置数据包括：

  • 全部学生编号，均为长度为 99 的由十进制数字字符构成的字符串，保证它们互不相同。
  • 系统开始日期，格式为 YYYY-MM-DD\texttt{YYYY-MM-DD}，保证该日期真实存在。
  • 系统结束日期，格式为 YYYY-MM-DD\texttt{YYYY-MM-DD}，保证该日期真实存在且不早于开始日期。
  • 场地个数，记它为正整数 num\textit{num}，则场地编号为 1,2,⋯ ,num1,2,\cdots,\textit{num}。
  • 对于每个场地，记其编号为 id\textit{id}，给定其纬度区间 [latLid,latRid][\textit{latL}_{\textit{id}},\textit{latR}_{\textit{id}}] 和经度区间 [lngLid,lngRid][\textit{lngL}_{\textit{id}},\textit{lngR}_{\textit{id}}]。

一条跑步锻炼记录包括：

  • 学生编号，一个长度为 99 的由十进制数字字符构成的字符串，保证学生编号存在。
  • 开始时间，格式为 YYYY-MM-DD hh:mm:ss\texttt{YYYY-MM-DD hh:mm:ss}，保证该时间真实存在。
  • 结束时间，格式为 YYYY-MM-DD hh:mm:ss\texttt{YYYY-MM-DD hh:mm:ss}，保证该时间真实存在且晚于开始时间。
  • 场地编号，一个正整数，保证场地编号存在。
  • 经纬度坐标序列，格式为 cnt lat1 lng1 lat2 lng2 ⋯ latcnt lngcnt\textit{cnt}\texttt{ }\textit{lat}_1\texttt{ }\textit{lng}_1\texttt{ }\textit{lat}_2\texttt{ }\textit{lng}_2\texttt{ }\cdots\texttt{ }\textit{lat}_{\textit{cnt}}\texttt{ }\textit{lng}_{\textit{cnt}}。

一条跑步锻炼记录是有效的，当且仅当它满足以下要求：

  • 开始时间和结束时间都在系统开始日期（含）和系统结束日期（含）之间。
  • 开始时间和结束时间在同一天，且都在当天的 06:00:00\texttt{06:00:00}（含）和 22:00:00\texttt{22:00:00}（含）之间。
  • 该学生当天尚无有效的跑步锻炼记录。
  • 跑步时长在 44 分钟（含）和 1212 分钟（含）之间。
    • 跑步时长的秒数等于从开始时间起向后数多少秒会到达结束时间。
  • 场地内坐标个数不少于总坐标个数的 85%85\%。
    • 要求即 ∑i=1cnt[latLid≤lati≤latRid][lngLid≤lngi≤lngRid]≥85%⋅cnt\displaystyle\sum_{i=1}^{\textit{cnt}}[\textit{latL}_{\textit{id}}\le\textit{lat}_i\le\textit{latR}_{\textit{id}}][\textit{lngL}_{\textit{id}}\le\textit{lng}_i\le\textit{lngR}_{\textit{id}}]\ge85\%\cdot\textit{cnt}。
    • 上式中，id\textit{id} 表示场地编号。条件 PP 为真时，[P]=1[P]=1；否则，[P]=0[P]=0。
  • 跑步距离不低于 1.21.2 千米，用 Haversine 公式估算。

    • 要求即 R∑i=1cnt−1dis(lati,lngi,lati+1,lngi+1)≥1.2\displaystyle R\sum_{i=1}^{\textit{cnt}-1}\textit{dis}(\textit{lat}_i,\textit{lng}_i,\textit{lat}_{i+1},\textit{lng}_{i+1})\ge1.2。

    • 上式中，RR 表示地球半径（单位：千米），取 R=6371R=6371；

      而 dis(lati,lngi,lati+1,lngi+1)\textit{dis}(\textit{lat}_i,\textit{lng}_i,\textit{lat}_{i+1},\textit{lng}_{i+1}) 的计算公式是

      2arcsin⁡sin⁡2(lati+1−lati)π360+sin⁡2(lngi+1−lngi)π360cos⁡latiπ180cos⁡lati+1π1802\arcsin\sqrt{\sin^2\frac{(\textit{lat}_{i+1}-\textit{lat}_i)\pi}{360}+\sin^2\frac{(\textit{lng}_{i+1}-\textit{lng}_i)\pi}{360}\cos\frac{\textit{lat}_i\pi}{180}\cos\frac{\textit{lat}_{i+1}\pi}{180}}

统计并输出每位学生的有效跑步锻炼次数。

提示：对于 C++ 语言，cmath 头文件中定义了 sqrt、sin、cos、asin、acos 等常用数学函数。其中，sqrt 表示开根，asin、acos 分别表示 arcsin⁡\arcsin、arccos⁡\arccos。可以借助 π=arccos⁡(−1)\pi=\arccos(-1) 来得到精确的 π\pi。

输入格式

第一行一个整数 nn，表示学生的个数。

第二行 nn 个长度为 99 的数字字符串，表示全部学生编号。

第三行是系统开始日期和系统结束日期，格式均为 YYYY-MM-DD\texttt{YYYY-MM-DD}，中间用一个空格隔开。

第四行一个整数 num\textit{num}，表示场地个数。

接下来 num\textit{num} 行，每行四个实数 latLid,latRid,lngLid,lngRid\textit{latL}_{\textit{id}},\textit{latR}_{\textit{id}},\textit{lngL}_{\textit{id}},\textit{lngR}_{\textit{id}}。

然后是一行一个整数 mm，表示跑步锻炼记录的条数。

接下来，对于每条跑步锻炼记录，输入四行，内容依次是：

  • 第一行一个长度为 99 的数字字符串，表示学生编号。
  • 第二行是开始时间和结束时间，格式均为 YYYY-MM-DD hh:mm:ss\texttt{YYYY-MM-DD hh:mm:ss}，中间用一个空格隔开。
  • 第三行一个整数，表示场地编号。
  • 第四行是经纬度坐标序列，格式为 cnt lat1 lng1 lat2 lng2 ⋯ latcnt lngcnt\textit{cnt}\texttt{ }\textit{lat}_1\texttt{ }\textit{lng}_1\texttt{ }\textit{lat}_2\texttt{ }\textit{lng}_2\texttt{ }\cdots\texttt{ }\textit{lat}_{\textit{cnt}}\texttt{ }\textit{lng}_{\textit{cnt}}。

保证纬度都在 [−90,90][-90,90] 内，经度都在 [−180,180][-180,180] 内。

保证输入合法，满足题目描述中保证的内容，甚至比较符合现实。

保证输入量不超过 5050 MB。

输出格式

输出 nn 行，每行一个数字字符串和一个整数，分别表示学生编号和有效跑步锻炼次数。

注意：输出顺序须与输入顺序（输入的第二行）相同。

样例

样例 1

输入

2
213251001
213241666
2025-09-01 2025-12-31
1
32.05549877074382 32.05705455752449 118.79193621876698 118.79314926886309
3
213251001
2025-12-07 06:10:14 2025-12-07 06:21:22
1
75 32.05676323801185 118.79214140497218 32.05690757003848 118.79216764715885 32.05696005441181 118.79229448439439 32.05697317550514 118.79247380600324 32.05696880180736 118.7926531276121 32.0569425596207 118.79281932812762 32.05691631743404 118.79298552864316 32.05675011691851 118.79302489192314 32.05659266379854 118.79300739713203 32.05641334218969 118.79298552864316 32.05627338386082 118.79297240754983 32.05608094115863 118.79293741796761 32.05592786173644 118.79291554947872 32.05578790340757 118.79288493359428 32.05572667163869 118.79277121745208 32.05575728752314 118.79253066407435 32.05576603491869 118.79232510027883 32.05578790340757 118.79216764715885 32.05586225626978 118.79204955731888 32.05611593074084 118.79207142580776 32.05626901016304 118.79207142580776 32.05645270546967 118.79209766799443 32.05661015858965 118.79211516278554 32.05673262212741 118.79214577866996 32.05684633826961 118.79218076825218 32.05693818592292 118.79228573699883 32.05695568071403 118.7924256953277 32.05696005441181 118.79258314844766 32.05696005441181 118.79271435938098 32.05695130701626 118.79285869140762 32.05683321717628 118.7930117708298 32.05666264296297 118.79302051822536 32.05647457395856 118.79300302343425 32.05630399974526 118.7929767812476 32.05614217292751 118.79296803385205 32.05596722501643 118.79292867057205 32.05581414559423 118.7928805598965 32.05572667163869 118.79274497526542 32.05575291382536 118.79256565365657 32.05579665080312 118.79235571616326 32.05582289298979 118.79217202085663 32.05592786173644 118.79204955731888 32.05605032527419 118.79204080992332 32.0562208994875 118.79207579950554 32.05638272630524 118.79207142580776 32.05655330051854 118.79211078908776 32.05670637994074 118.79213703127441 32.05683321717628 118.79219388934551 32.05691194373626 118.7923119791855 32.05694693331848 118.79244756381658 32.05693818592292 118.79257440105211 32.05692506482959 118.79272310677653 32.05687258045627 118.79284557031428 32.05681134868739 118.79295053906094 32.05668888514963 118.79300302343425 32.056544553123 118.79298115494538 32.0563914737008 118.79296366015427 32.05626901016304 118.79294179166538 32.05611155704307 118.79291554947872 32.05597597241199 118.7928805598965 32.05585788257201 118.79284119661651 32.0557835297098 118.79277121745208 32.0557835297098 118.79260939063433 32.05579665080312 118.79246943230547 32.05583601408312 118.79229885809217 32.05588953982577 118.79211953648331 32.05599450857242 118.79207142580776 32.05619569867016 118.79205393101665 32.05632253590569 118.79209329429665 32.05649748381677 118.79211078908776 32.0567205424034 118.7921763945544 32.05682551115004 118.79222887892773 32.05688674291893 118.79232947397661 32.05692714756825 118.79250004818991 32.05692277387047 118.79270561198543
213251001
2025-12-06 23:59:59 2025-12-07 00:00:00
1
1 32.05549877074382 118.79314926886309
213241666
2025-12-07 06:15:10 2025-12-07 06:20:10
1
40 32.06026324 118.7956414 32.05696005 118.79229448 32.0569688 118.79265313 32.05691632 118.79298553 32.05659266 118.7930074 32.05991334 118.79648553 32.05608094 118.79293742 32.0557879 118.79288493 32.05575729 118.79253066 32.0557879 118.79216765 32.05961593 118.79557143 32.05645271 118.79209767 32.05673262 118.79214578 32.05693819 118.79228574 32.05696005 118.79258315 32.06046005 118.79621436 32.05683322 118.79301177 32.05647457 118.79300302 32.05614217 118.79296803 32.05581415 118.79288056 32.05925291 118.79606565 32.05582289 118.79217202 32.05605033 118.79204081 32.05638273 118.79207143 32.05670638 118.79213703 32.06033322 118.79569389 32.05694693 118.79244756 32.05692506 118.79272311 32.05681135 118.79295054 32.05654455 118.79298115 32.05976901 118.79644179 32.05597597 118.79288056 32.05578353 118.79277122 32.05579665 118.79246943 32.05588954 118.79211954 32.05949451 118.79557143 32.05632254 118.79209329 32.05672054 118.79217639 32.05688674 118.79232947 32.05692377 118.7926589

输出

213251001 1
213241666 0

解释

后两条跑步锻炼记录无效：

  • 第二条记录：开始时间和结束时间不在同一天，时长少于 44 分钟，且距离为 00。
  • 第三条记录：场地内坐标个数少于总坐标个数的 85%85\%。

样例 2

见附加文件中的 exercise_sample2.in 和 exercise_sample2.ans。

seuOJ Powered by SYZOJ.