【BZOJ】【P 108】【POI 2007】【天然ガス配管Gaz】【題解】【数学】

795 ワード

転送ゲート:http://www.lydsy.com/JudgeOnline/problem.php?id=1108
この問題の重点は「南向きか東向き」です.
そして、二つの黒い点A:(x 1,y 1)とB:(x 2,y 2)の白点C:(x 3,y 3)D:(x 4,y 4)(x 3,x 4>x 1,x 2)(y 3,y 4二つの案
一:A->C B->D
価格:(x 3-x 1)+(y 1-y 3)+(x 4-x 2)+(y 2-y 4)
二:A->D B->C
価格:(x 4-x 1)+(y 1-y 4)+(x 3-x 2)+(y 2-y 3)
これは等価です.
簡単に紹介されます.テーマに合うなら、どんなマッチ案の価格も同じです.
そして答えは全ての黒点の和(y-x)と白点の和(x-y)の和です.
コード:
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,x,y;long long ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x,&y),ans+=y-x;		
	for(int i=1;i<=n;i++)
		scanf("%d%d",&x,&y),ans+=x-y;
	cout<<ans<<endl;
	return 0;
}