efefjljfelkelkf

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include<bits/stdc++.h>
#define data long long
#define pb push_back
#define fi first
#define se second
const int N=1505;
using namespace std;
data ct,s[2],sum[N],tot;
int T,n,m;
bool flg[N];
vector<pair<int,int>>g[N];

struct vec{
    data x,y; int id;
    data operator*(const vec &b)const{
        return x*b.y-y*b.x;
    }
    data operator%(const vec&b)const{
        return x*b.x+y*b.y;
    }
    vec operator-(const vec&b)const{
        return vec{x-b.x,y-b.y,id};
    }
    bool operator==(const vec&b)const{
        return x==b.x&&y==b.y;
    }
} p[N],a[N*2];
int cmp(const vec&A,const vec&B){
    if(A.y==0&&B.y==0) return A.x>0&&B.x<0;
    if(A.y==0)return A.x>0||B.y<0;
    if(B.y==0) return B.x<0&&A.y>0;
    if((A.y>0)^(B.y>0)) return A.y>0;
    return (A*B)>0;
}

void chg(int x){
    s[flg[x]]-=sum[x];
    s[flg[x]^1]+=sum[x];
    for (auto v:g[x]){
        if (flg[v.fi]!=flg[x]) ct-=v.se; else ct+=v.se;
    }
    flg[x]^=1;
}
int main(){
    scanf("%d",&T);

    while(T--){
        scanf("%d%d",&n,&m);
        data ansp=1,ansq=0;
        for (int i=1;i<=n;i++) sum[i]=0,flg[i]=0;
        for (int i=1;i<=n;i++) {scanf("%lld%lld",&p[i].x,&p[i].y); p[i].id=i;}
        for (int i=1;i<=m;i++){
            data x,y;data z;
            scanf("%lld%lld%lld",&x,&y,&z);
            g[x].pb({y,z}); g[y].pb({x,z});
            sum[x]+=z,sum[y]+=z; tot+=z;
        }
        for (int i=1;i<=n;i++){
            vector<vec>a; a.clear();
            for (int j=1;j<=n;j++)
            if (j!=i) a.pb(p[j]-p[i]);
            sort(a.begin(),a.end(),cmp);

            //for (int j=0;j<n-1;j++) printf("(%lld, %lld, %d) ",a[j].x,a[j].y,a[j].id); puts("");

            for (int j=0;j<n-1;j++) a.pb(a[j]);
            int l=0,r=1;

            ct=0; s[0]=tot*2; s[1]=0;
            for (int j=1;j<=n;j++) flg[j]=0; chg(i); chg(a[0].id);
            //f


            for (;l<n;){
                while(r<=l||a[l]*a[r]>0||(a[l]*a[r]==0&&a[l]%a[r]>0&&!(a[l]==a[r]))){
                    chg(a[r].id);
                    r++;
                }
                //printf("%d %d : ",l,r); for (int i=1;i<=n;i++) printf("%d ",flg[i]); puts("");
                if (ansp*(s[1]*s[0])>ct*(s[1]+s[0])*ansq){
                    ansp=ct*(s[1]+s[0]);
                    ansq=s[1]*s[0];
                    data k=__gcd(ansp,ansq);
                    ansp/=k,ansq/=k;
                }
                while(a[l]*a[l+1]==0&&a[l]%a[l+1]>0&&l<n) chg(a[l++].id);
                chg(a[l++].id); ;
            }
            printf("%lld/%lld\n",ansp,ansq);
        }
        //printf("%lld/%lld\n",ansp,ansq);
    }
}

#include

#define data long long

#define pb push_back

#define fi first

#define se second

const int N=1505;

using namespace std;

data ct,s[2],sum[N],tot;

int T,n,m;

bool flg[N];

vector>g[N];

struct vec{

data x,y; int id;

data operator*(const vec &b)const{

return x*b.y-y*b.x;

}

data operator%(const vec&b)const{

return x*b.x+y*b.y;

}

vec operator-(const vec&b)const{

return vec{x-b.x,y-b.y,id};

}

bool operator==(const vec&b)const{

return x==b.x&&y==b.y;

}

} p[N],a[N*2];

int cmp(const vec&A,const vec&B){

if(A.y==0&&B.y==0) return A.x>0&&B.x<0;

if(A.y==0)return A.x>0||B.y<0;

if(B.y==0) return B.x<0&&A.y>0;

if((A.y>0)^(B.y>0)) return A.y>0;

return (A*B)>0;

}

void chg(int x){

s[flg[x]]-=sum[x];

s[flg[x]^1]+=sum[x];

for (auto v:g[x]){

if (flg[v.fi]!=flg[x]) ct-=v.se; else ct+=v.se;

}

flg[x]^=1;

}

int main(){

scanf("%d",&T);

while(T--){

scanf("%d%d",&n,&m);

data ansp=1,ansq=0;

for (int i=1;i<=n;i++) sum[i]=0,flg[i]=0;

for (int i=1;i<=n;i++) {scanf("%lld%lld",&p[i].x,&p[i].y); p[i].id=i;}

for (int i=1;i<=m;i++){

data x,y;data z;

scanf("%lld%lld%lld",&x,&y,&z);

g[x].pb({y,z}); g[y].pb({x,z});

sum[x]+=z,sum[y]+=z; tot+=z;

}

for (int i=1;i<=n;i++){

vectora; a.clear();

for (int j=1;j<=n;j++)

if (j!=i) a.pb(p[j]-p[i]);

sort(a.begin(),a.end(),cmp);

//for (int j=0;j

for (int j=0;j

int l=0,r=1;

ct=0; s[0]=tot*2; s[1]=0;

for (int j=1;j<=n;j++) flg[j]=0; chg(i); chg(a[0].id);

//f

for (;l

while(r<=l||a[l]*a[r]>0||(a[l]*a[r]==0&&a[l]%a[r]>0&&!(a[l]==a[r]))){

chg(a[r].id);

r++;

}

//printf("%d %d : ",l,r); for (int i=1;i<=n;i++) printf("%d ",flg[i]); puts("");

if (ansp*(s[1]*s[0])>ct*(s[1]+s[0])*ansq){

ansp=ct*(s[1]+s[0]);

ansq=s[1]*s[0];

data k=__gcd(ansp,ansq);

ansp/=k,ansq/=k;

}

while(a[l]*a[l+1]==0&&a[l]%a[l+1]>0&&l

chg(a[l++].id); ;

}

printf("%lld/%lld\n",ansp,ansq);

}

//printf("%lld/%lld\n",ansp,ansq);

}

}