CSAcademy Beta Round #5 Force Graph

题目链接：https://csacademy.com/contest/arhiva/#task/force_graph/

大意是有若干个节点，每个节点对应一个二维坐标，节点之间相互有斥力存在。同时有些节点之间有变存在。对于有边存在的节点，他们互相的斥力大小为F1*dis值，否则则为F2*dis值，其中dis值为节点之间的欧氏距离。问每个节点受到的斥力大小。

这个其实就是很简单的数学推一下：先假设所有的点都受到F2*dis值，然后再加上所有有边的其他节点的斥力修正。

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <cassert>
#include <set>
using namespace std;


const int N=323456;


struct Edge {
    int to,next;
    Edge() {}
    Edge(int _to,int _next):to(_to),next(_next) {}
} edge[N<<2];
int idx=1,head[N];
inline void addedge(int u,int v) {
    edge[++idx]=Edge(v,head[u]);
    head[u]=idx;
}

long long x[N],y[N];
int main () {
    int n,m;
    long long f1,f2;
    while (scanf("%d %d %lld %lld",&n,&m,&f1,&f2)==4) {
        idx=1;memset(head,0,sizeof head);
        for (int i=1;i<=m;i++) {
            int u,v;
            scanf("%d %d",&u,&v);
            addedge(u,v);
            addedge(v,u);
        }
        long long sx=0,sy=0;
        for (int i=1;i<=n;i++) {
            scanf("%lld %lld",x+i,y+i);
            sx+=x[i];sy+=y[i];
        }
        for (int i=1;i<=n;i++) {
            long long rx=(x[i]*n-sx)*f2;
            long long ry=(y[i]*n-sy)*f2;
            for (int k=head[i];k;k=edge[k].next) {
                int j=edge[k].to;
                long long dx=x[i]-x[j],dy=y[i]-y[j];
                rx+=dx*(f1-f2);ry+=dy*(f1-f2);
            }
            cout<<rx<<" "<<ry<<endl;
        }
    }
    return 0;
}