2014
03-06

Balance

A sailboat has many forces acting on it. This allows it to sail in many different directions, even if the wind is not blowing in the desired direction. In order for the boat to be easily controlled, however, certain forces must be balanced.

Suppose the wind is blowing from the north and the boat is facing west. Above the water, the blowing wind hits the sails, and because of the way that they are angled, pushes the boat to the southwest. The keel extends deep below the water. The water resistance on the keel creates a counterforce pushing the boat northward. Ideally, the northward force on the keel will counteract the southward component of the force on the sails, so that the boat will move to the west.

A problem can arise if the centre of the sails (called the Centre of Effort, or CE) is not directly above the centre of the keel (called the Centre of Lateral Resistance, or CLR). In general, the boat can pivot about the centre of the keel. If the sails are too far forward of the keel, the wind will push the bow (the front) of the boat southwards, and the boat will turn towards the south. If the sails are too far aft of (behind) the keel, the wind will push the stern (the back) southwards, and the boat will turn towards the north. Ideally, the sails and keel are balanced so that the boat sails in a straight line.

In this problem, you will examine a side view of the boat to determine whether the CE is above the CLR. The CE is defined as the centroid of the part of the boat above the waterline. The CLR is defined as the centroid of the part of the boat below the waterline. The centroid of a polygon is the unique point such that any line passing through it divides the polygon into two halves of equal area.

The first line of input will contain a single integer n specifying the number of points along the outline of the side view of the boat. The following n lines will each contain two integers: the x and y coordinate of a point along the outline. The points will be given in order along the outline. The x axis (i.e. the line y = 0) represents the waterline. Assume that the boat faces in the direction of increasing x coordinates.

The first line of input will contain a single integer n specifying the number of points along the outline of the side view of the boat. The following n lines will each contain two integers: the x and y coordinate of a point along the outline. The points will be given in order along the outline. The x axis (i.e. the line y = 0) represents the waterline. Assume that the boat faces in the direction of increasing x coordinates.

7
0 1
2 3
4 1
4 -3
2 -3
2 -1
0 -1

CE is aft of CLR by 0.50 units.

#include<iostream>
#include<queue>
using namespace std;
const int N = 1005;          //有N头牛
const int INF = 0x3f3f3f3f;  //定义一个大数作为无穷大
int NUM;                     //前向星变量，记录边数
bool flag[N];                //标记是否在队列
int dis[N];                  //标记1到其他顶点的最短距离
int sum[N];                  //标记入队次用，用于判断负环

struct Node{                 //记录关系
int v,w,next;            //目标点，权值，下一点索引
}node[20005];

void add(int a,int b,int c){ //前向星加边函数
node[NUM].v = b;
node[NUM].w = c;
}

int SPFA(int s,int n){
int i;
for(i=0;i<=n;i++){
sum[i] = 0;         //初始化所有点入队次数为0
flag[i] = false;    //初始化队列标记，false为未入队
dis[i] = INF;       //初始化1到其他顶点距离为无穷大
}
queue<int> q;           //定义一个队列，存放维护的点
q.push(s);              //把源点放进队列
dis[s]=0;               //到自身距离为0
while(!q.empty()){      //若队列不为空
int u = q.front();  //取队列头元素
q.pop();            //取元素后，元素弹出
flag[u] = false;    //标记为不在队列
{ //遍历与U相连的所有点
int v = node[i].v;            //终点
int w = node[i].w;            //起点到终点权值
if(dis[v] > dis[u] + w)
{      //
dis[v] = dis[u] + w;
if(!flag[v])
{             //若不再队列
q.push(v);            //把点放进队列维护
flag[v] = true;       //标记为在队列
if(++sum[v] > n)
{     //入队数++，如果超过n，存在负环
return -1;
}
}
}
}

}
if(dis[n] == INF) return -2;
return dis[n];
}

int main(){
int n,ml,md,a,b,c;
while(scanf("%d%d%d",&n,&ml,&md)!=EOF){
NUM = 0;
while(ml--){                     //喜欢
scanf("%d%d%d",&a,&b,&c);
}
while(md--){                     //不喜欢
scanf("%d%d%d",&a,&b,&c);
}
printf("%d\n",SPFA(1,n));
}
return 0;
}