现在的位置: 首页 > 算法 > 正文

poj2187 凸包直径模板

2019年09月07日 算法 ⁄ 共 1145字 ⁄ 字号 评论关闭
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
#define INF 50005
struct Node
{
    double x, y;
};
Node point[INF];
int n, s[INF], top;
double cross(Node a, Node b, Node c)
{
    double x1 = a.x - c.x;
    double y1 = a.y - c.y;
    double x2 = b.x - c.x;
    double y2 = b.y - c.y;
    return x1 * y2 >= x2 * y1;
}
double dis(Node a, Node b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int cmp(Node a, Node b)
{
    if(a.y==b.y)
        return a.x<b.x;
    return a.y<b.y;
}
void graham()
{
    int i;
    sort(point, point+n, cmp);
    top = 1;
    s[0] = 0;
    s[1] = 1;
    s[2] = 2;
    for (i=2; i<n; i++)
    {
        while (top && cross(point[i], point[s[top]], point[s[top-1]]))
            top--;
        s[++top] = i;
    }
    int len = top;
    s[++top] = n - 2;
    for (i=n-3; i>=0; i--)
    {
         while (len!=top && cross(point[i], point[s[top]], point[s[top-1]]))
            top--;
        s[++top] = i;
    }
}
int main()
{
    int i, j;
    while (scanf("%d", &n)!=EOF)
    {
         for (i=0; i<n; i++)
            scanf("%lf%lf", &point[i].x, &point[i].y);
        if (n<3)
            printf("%.lf\n", dis(point[0], point[1]));
        else
        {
        graham();
        double ans = 0;
          for(i = 0; i < top-1; i ++)
            for(j = i+1; j < top; j ++)
                ans = max(ans, dis(point[s[i]], point[s[j]]));//G++用%f
        printf("%.lf\n", ans);
        }
    }
    return 0;
}

再一次遇到这一题时,相同的代码wrong到死

在老师的帮助下找到原因

如果输出的是小数,在G++用"%f"输出就能AC,而用"%lf"输出就会WA,而C++就没这个问题。
ISO C只允许用%f输出小数,%lf属于非标准用法。(http://poj.org/page?id=1000 Other questions一节)



抱歉!评论已关闭.