首先有一个三分的思路：
考虑每个指针与某个给定指针的偏角，在一分钟内为单谷函数
给它们取max还是单谷函数，于是可以是三分
check的时候貌似可以set优化，%zjx，我就先咕了
正解的话考虑二分
发现对于一个给定的偏角范围，每个指针都有一个合法区间
于是对区间求交集，用珂朵莉树实现
最后特殊处理一下时针范围对分针范围的限制即可
Code:
#include <bits/stdc++.h>
using namespace std;
#define N 100010
#define ll long long
//#define int long long
char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
inline int read() {
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48), c=getchar();
return ans*f;
}
int n, lst;
int p[N];
const double step1=360.0/43200.0;
const double step2=360.0/3600.0;
const double eps=1e-10;
namespace force{
inline double calch(int a, int b) {
a%=43200, b%=43200;
double t1=step1*a, t2=step1*b, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calcm(int a, int b) {
a%=3600, b%=3600;
double t1=a*step2, t2=b*step2, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
void solve() {
double ans=360;
for (int i=1,a,b,c; i<=n; ++i) {
a=read(); b=read(); c=read();
p[i]=a*3600+b*60+c;
}
for (int i=0; i<43200; ++i) {
double dlth=0, dltm=0;
for (int j=1; j<=n; ++j) {
dlth=max(dlth, calch(i, p[j]));
dltm=max(dltm, calcm(i, p[j]));
}
// cout<<"dlt: "<<dlth<<' '<<dltm<<endl;
ans=min(ans, max(dlth, dltm));
}
printf("%.7lf\n", ans);
exit(0);
}
}
namespace task1{
inline double calch(double a, int b) {
b%=43200;
double t1=step1*a, t2=step1*b, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calcm(double a, int b) {
b%=3600;
double t1=a*step2, t2=b*step2, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calc(int h, double t) {
double ans=0;
for (int i=1; i<=n; ++i) {
ans=max(ans, calch(t+h*60, p[i]));
ans=max(ans, calcm(t+(h%60)*60, p[i]));
}
return ans;
}
void solve() {
double ans=360;
for (int i=0; i<720; ++i) {
double lside=0, rside=60, lmid, rmid, tem;
for (int j=1; j<=50; ++j) {
// cout<<"ij: "<<i<<' '<<j<<' '<<lside<<' '<<rside<<' '<<calc(i, lmid)<<' '<<calc(i, rmid)<<endl;
lmid=lside+(rside-lside)/3.0, rmid=lside+2.0*(rside-lside)/3.0;
if ((tem=calc(i, lmid))<calc(i, rmid)) rside=rmid;
else lside=lmid;
// if (j>5 && tem>ans+5) break;
}
ans=min(ans, calc(i, lside));
}
printf("%.10lf\n", ans);
exit(0);
}
}
namespace task2{
int sta[N];
inline double calch(double a, int b) {
b%=43200;
double t1=step1*a, t2=step1*b, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calcm(double a, int b) {
b%=3600;
double t1=a*step2, t2=b*step2, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calc(int h, double t) {
double ans=0;
for (int i=1; i<=n; ++i) {
ans=max(ans, calch(t+h*60, p[i]));
ans=max(ans, calcm(t+(h%60)*60, p[i]));
}
return ans;
}
void solve() {
random_device(seed);
srand(seed());
double ans=360;
for (int i=0; i<720; ++i) sta[i]=i;
random_shuffle(sta+1, sta+n+1);
for (int i=0; i<720; ++i) {
// cout<<"i: "<<i<<endl;
if (clock()>1900000) break;
double lside=0, rside=60, lmid, rmid, tem;
for (int j=1; j<=50; ++j) {
// cout<<"ij: "<<i<<' '<<j<<' '<<lside<<' '<<rside<<' '<<calc(i, lmid)<<' '<<calc(i, rmid)<<endl;
lmid=lside+(rside-lside)/3.0, rmid=lside+2.0*(rside-lside)/3.0;
if ((tem=calc(sta[i], lmid))<calc(sta[i], rmid)) rside=rmid;
else lside=lmid;
if (j>5 && tem>ans+2) break;
if (j>10 && tem>ans+0.1) break;
if (j>20 && tem>ans+0.005) break;
}
ans=min(ans, calc(sta[i], lside));
}
printf("%.10lf\n", ans);
exit(0);
}
}
namespace task3{
int p[N];
inline double calch(double a, int b) {
b%=43200;
double t1=step1*a, t2=step1*b, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calcm(double a, int b) {
b%=3600;
double t1=a*step2, t2=b*step2, ans=max(t1, t2)-min(t1, t2);
if (ans>180.0) ans=360.0-ans;
return ans;
}
inline double calc(int h, double t) {
double ans=0;
for (int i=1; i<=n; ++i) {
ans=max(ans, calch(t+h*60, p[i]));
ans=max(ans, calcm(t+(h%60)*60, p[i]));
}
return ans;
}
void solve() {
double ans=360;
for (int i=lst*60; i<=lst*60+30; ++i) {
// cout<<"i: "<<i<<endl;
if (clock()>1700000) break;
double lside=0, rside=60, lmid, rmid, tem;
for (int j=1; j<=50; ++j) {
// cout<<"ij: "<<i<<' '<<j<<' '<<lside<<' '<<rside<<' '<<calc(i, lmid)<<' '<<calc(i, rmid)<<endl;
lmid=lside+(rside-lside)/3.0, rmid=lside+2.0*(rside-lside)/3.0;
if ((tem=calc(i, lmid))<calc(i, rmid)) rside=rmid;
else lside=lmid;
// if (j>5 && tem>ans+5) break;
// if (j>10 && tem>ans+1) break;
// if (j>20 && tem>ans+0.5) break;
}
ans=min(ans, calc(i, lside));
}
printf("%.10lf\n", ans);
exit(0);
}
}
namespace task{
int top, rtop;
double sta[N];
struct odt{
struct node{
double l, r;
node(double a, double b):l(a),r(b){}
friend inline bool operator < (node a, node b) {return a.l<b.l;}
};
set<node> s;
odt(){s.insert(node(0.0, 360.0-eps));}
inline void clear() {s.clear(); s.insert(node(0.0, 360.0-eps));}
set<node>::iterator split(double pos) {
auto it=s.lower_bound(node(pos, 0));
if (it!=s.end() && it->l==pos) return it;
--it; node tem=*it; s.erase(it);
s.insert(node(tem.l, pos-eps));
return s.insert(node(pos, tem.r)).first;
}
void ins1(double l, double r) {
// cout<<"ins1: "<<l<<' '<<r<<endl;
auto it=s.lower_bound(node(l, 0));
if (it!=s.begin()) {
--it;
// printf("it: %.6lf %.6lf\n", it->l, it->r);
if (it->r>=l) it=split(l);
else ++it;
}
if (it!=s.begin()) s.erase(s.begin(), it);
it=s.lower_bound(node(r+eps, 0));
if (it!=s.begin()) {
--it;
if (it->r>r) it=split(r+eps);
else ++it;
}
if (it!=s.end()) s.erase(it, s.end());
}
void ins2(double l, double r) {
// cout<<"ins2: "<<l<<' '<<r<<endl;
auto it1=s.lower_bound(node(l+eps, 0));
if (it1!=s.begin()) {
--it1;
if (it1->r>=l) it1=split(l+eps);
else ++it1;
}
auto it2=s.lower_bound(node(r, 0));
if (it2!=s.begin()) {
--it2;
if (it2->r>r) it2=split(r);
else ++it2;
}
it1=s.lower_bound(node(l+eps, 0));
if (it1!=it2) s.erase(it1, it2);
}
double maxlenth() {
double ans=0;
for (auto it:s) ans=max(ans, it.r-it.l);
return ans;
}
void del(double l, double r) {
// cout<<"del: "<<l<<' '<<r<<endl;
auto it=s.lower_bound(node(l, 0));
if (it!=s.begin()) {
--it;
if (it->r>l) it=split(l);
else ++it;
}
// printf("it: %.6lf %.6lf\n", it->l, it->r);
it=s.lower_bound(node(r, 0));
if (it!=s.begin()) {
--it;
if (it->r>=r) it=split(r);
else ++it;
}
auto it1=s.lower_bound(node(l, 0)), it2=it;
if (it1!=it2) s.erase(it1, it2);
}
}tr1, tr2, tr;
struct range{
double l, r;
inline void build(double a, double b) {l=a; r=b;}
friend inline bool operator < (range a, range b) {return a.l<b.l;}
}rg[N];
bool check(double dlt) {
// cout<<"check: "<<dlt<<endl;
tr1.clear(); tr2.clear();
for (int j=1; j<=n; ++j) {
// cout<<"j: "<<j<<endl;
int k;
double now;
k=p[j]%43200;
now=k*step1;
// cout<<"now: "<<now<<endl;
if (now-dlt<0) tr1.ins2(now+dlt, 360.0+(now-dlt));
else if (now+dlt>=360.0) tr1.ins2(now+dlt-360.0, now-dlt);
else tr1.ins1(now-dlt, now+dlt);
k=p[j]%3600;
now=k*step2;
// cout<<"now: "<<now<<endl;
if (now-dlt<0) tr2.ins2(now+dlt, 360.0+(now-dlt));
else if (now+dlt>=360.0) tr2.ins2(now+dlt-360.0, now-dlt);
else tr2.ins1(now-dlt, now+dlt);
// cout<<"s1: "; for (auto it:tr1.s) cout<<it.l<<','<<it.r<<' '; cout<<endl;
// cout<<"s2: "; for (auto it:tr2.s) cout<<it.l<<','<<it.r<<' '; cout<<endl;
}
// cout<<"return "<<(tr1.s.size()&&tr2.s.size())<<endl;
if (!(tr1.s.size()&&tr2.s.size())) return 0;
if (tr1.maxlenth()>=30.0) return 1;
// cout<<"tr1: "; for (auto it:tr1.s) cout<<fixed<<setprecision(10)<<it.l<<','<<it.r<<' '; cout<<endl;
// cout<<"tr2: "; for (auto it:tr2.s) cout<<fixed<<setprecision(10)<<it.l<<','<<it.r<<' '; cout<<endl;
rtop=0;
for (auto it:tr1.s) {
double l=it.l, r=it.r;
int a=floor(l/30), b=floor(r/30);
if (a==b) rg[++rtop].build((l-30.0*a)*12.0, (r-30.0*b)*12.0);
else {
rg[++rtop].build(0, (r-30.0*b)*12.0);
rg[++rtop].build((l-30.0*a)*12.0, 360.0);
}
}
sort(rg+1, rg+rtop+1);
range lst;
top=0; sta[++top]=0.0-eps;
for (int i=1; i<=rtop; ++i) {
if (i==1) lst=rg[i];
else if (lst.r<rg[i].l) {sta[++top]=lst.l; sta[++top]=lst.r; lst=rg[i];}
else lst.r=max(lst.r, rg[i].r);
}
if (rtop) sta[++top]=lst.l, sta[++top]=lst.r;
sta[++top]=360.0;
sort(sta+1, sta+top+1);
// cout<<"top: "<<top<<' '<<rtop<<endl;
// cout<<"rg: "; for (int i=1; i<=rtop; ++i) cout<<rg[i].l<<','<<rg[i].r<<' '; cout<<endl;
// cout<<"sta: "; for (int i=1; i<=top; ++i) cout<<sta[i]<<' '; cout<<endl;
for (int i=1; i<top&&rtop; i+=2) {
if (sta[i]+eps>sta[i+1]-eps) continue;
tr2.del(sta[i]+eps, sta[i+1]-eps);
// cout<<"tr1: "; for (auto it:tr1.s) cout<<fixed<<setprecision(10)<<it.l<<','<<it.r<<' '; cout<<endl;
// cout<<"tr2: "; for (auto it:tr2.s) cout<<fixed<<setprecision(10)<<it.l<<','<<it.r<<' '; cout<<endl;
}
return tr1.s.size()&&tr2.s.size();
}
void solve() {
// tr.ins2(47.6, 350); tr.ins1(47.3, 100);
// cout<<"s: "; for (auto it:tr.s) cout<<it.l<<','<<it.r<<' '; cout<<endl;
// exit(0);
// cout<<check(178.594)<<endl;
// exit(0);
double l=0, r=180.0-eps, mid;
bool tem;
for (int i=1; i<=50; ++i) {
mid=(l+r)/2;
// cout<<fixed<<setprecision(10)<<"mid: "<<l<<' '<<r<<' '<<mid<<endl;
if (tem=check(mid)) r=mid;
else l=mid;
// cout<<"return "<<tem<<endl;
}
printf("%.10lf\n", l);
exit(0);
}
}
signed main()
{
freopen("unreal.in", "r", stdin);
freopen("unreal.out", "w", stdout);
bool allsame=1;
n=read();
for (int i=1,a,b,c; i<=n; ++i) {
a=read(); b=read(); c=read();
if (i!=1 && a!=lst) allsame=0;
p[i]=a*3600+b*60+c;
lst=a;
}
// if (n<=1000) task1::solve();
// else task2::solve();
task::solve();
return 0;
}