退火大法好

我并不会正解于是只好打退火了……其他没啥好讲……只要对每一种颜色开一个vector，存一下所有这个颜色的位置，判定的时候可以去所有的颜色里二分找到前缀和后缀，把和当前点距离小的加入答案

然后就没有然后了……

//minamoto#include
    
     #define IT vector
     
      ::iterator#define R register#define double long double#define RD T*(rand()*2-RAND_MAX)#define fp(i,a,b) for(R int i=a,I=b+1;i
      
       I;--i)#define go(u) for(R int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e4+5;const double D=0.97,eps=1e-14;vector
       
        pos[N];double ans=1e10,pp,pr,T,res,best,pq,hp;int n,m,x,c,mn=1e5+5,mx=-1e5+5;IT it;double calc(R double x){    double r=0,p;    fp(i,1,n){        p=1e12;        it=lower_bound(pos[i].begin(),pos[i].end(),x);        if(it!=pos[i].end())p=min(p,(*it)-x);        if(it!=pos[i].begin())p=min(p,x-*(it-1));        r+=p*p;    }return r;}int main(){    srand(time(0));//  freopen("testdata.in","r",stdin);    n=read(),m=read();fp(i,1,m)x=read(),c=read(),pos[c].push_back(x),mn=min(mn,x),mx=max(mx,x);    pr=(1.0*mn+mx)/2,best=calc(pr);    while(clock()
        
         eps;T*=D){            pq=pp+RD,res=calc(pq);            if(best>res)best=res,pr=pq;            if(ans>res||exp((ans-res)/T)>(double)rand()/RAND_MAX)            ans=res,pp=pq;        }if(pr==hp)break;    }printf("%.4Lf\n",pr);}