UVALive 6772 - Crane Balancing

题目链接： UVALive link2 给了一个多边形。均匀分布的。问在一个端点可以加多重，可以保持平衡。简单题。首先要找出多边形的重心。重心找法就是进行三角剖分，然后加权平均就可以了。然后进行讨论几种情况，分别选取最左和最右的作为轴心点，然后就可以解决了。主要精度误差。

/* ***
Author :kuangbin
Created Time :2015/5/7 19:46:56
File Name :F:\ACM\2015ACM\比赛练习\2014final\C.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const double eps = 1e-8;
const double INF = 1e30;
const int MAXN = 110;
struct Point{
int x,y;
void input(){
scanf(“%d%d”,&x,&y);
}
}p[MAXN];

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1){
int Min = 100000;
int Max = -100000;
for(int i = 0;i < n;i++){
p[i].input();
if(p[i].y == 0){
Min = min(Min,p[i].x);
Max = max(Max,p[i].x);
}
}
double x = 0, y = 0;
double tot = 0;
for(int i = 0;i < n;i++){
int x1 = p[i].x;
int y1 = p[i].y;
int x2 = p[(i+1)%n].x;
int y2 = p[(i+1)%n].y;
double s = (x1*y2 - x2*y1)/2.0;
tot += s;
x += s(x1+x2)/3;
y += s(y1+y2)/3;
}
x /= tot;
y /= tot;
tot = fabs(tot);
double ans1;
double ans2;
bool flag = true;
if(p[0].x > Max){
if(x > Max+eps)flag = false;
else {
if(x < Min-eps)ans1 = tot(Min-x)/(p[0].x-Min);
else ans1 = 0;
ans2 = tot(Max-x)/(p[0].x-Max);
}
}
else if(p[0].x >= Min){
if(x > Min - eps && x < Max + eps){
ans1 = 0;
ans2 = INF;
}
else if(x > Max+eps){
if(p[0].x == Max)flag = false;
else {
ans1 = tot(x-Max)/(Max-p[0].x);
ans2 = INF;
}
}
else {
if(p[0].x == Min)flag = false;
else {
ans1 = tot(Min-x)/(p[0].x-Min);
}
}
}
else {
if(x < Min-eps)flag = false;
else {
if(x > Max+eps)ans1 = tot(x-Max)/(Max-p[0].x);
else ans1 = 0;
ans2 = tot(x-Min)/(Min-p[0].x);
}
}
if(!flag || ans1 > ans2)printf(“unstable\n”);
else {
printf(“%.0lf .. “,floor(ans1));
if(ans2 == INF)printf(“inf\n”);
else printf(“%.0lf\n”,ceil(ans2));
}
}
return 0;
}