不同的结果VS C ++和GNU g ++

问题描述

我有一个在VS C ++中工作的程序，不能和g ++一起工作。代码如下：

  #define _USE_MATH_DEFINES 
 
 #include< cmath> 
 #include< iostream> 
 #include< vector> 
 #include< cstdio> 
 #include< algorithm> 
 #include< set> 
 
 #define EP 1e-10 
 
 using namespace std; 
 
 typedef pair< long long，long long> II; 
 typedef pair< bool，int>双; 
 typedef vector< ii>七; 
 
 //返回二维空间中三个点的方向
 int orient2D（ii pt0，ii pt1，ii pt2）
 {
 long long result =（pt1 .first  -  pt0.first）*（pt2.second  -  pt0.second）
  - （pt1.second  -  pt0.second）*（pt2.first  -  pt0.first）; 
返回结果== 0？ 0：结果< 0？ -1：1; 
} 
 
 //返回由余弦定律导出的角度center-pt1-pt2。 
 //定义为负数，如果pt2在分段pt1的右侧以
为中心的双角（ii中心，ii pt1，ii pt2）
 {
 double aS = pow （center.first  -  pt1.first，2）+ pow（center.second  -  pt1.second，2）; 
 double bS = pow（pt2.first  -  pt1.first，2）+ pow（pt2.second  -  pt1.second，2）; 
 double cS = pow（center.first  -  pt2.first，2）+ pow（center.second  -  pt2.second，2）; 
 
 / * long long aS =（center.first  -  pt1.first）*（center.first  -  pt1.first）+（center.second  -  pt1.second）*（center.second  -  pt1 。第二）; 
 long long bS =（pt2.first  -  pt1.first）*（pt2.first  -  pt1.first）+（pt2.second  -  pt1.second）*（pt2.second  -  pt1.second）; 
 long long cS =（center.first  -  pt2.first）*（center.first  -  pt2.first）+（center.second  -  pt2.second）*（center.second  -  pt2.second）; * / 
 
 int sign = orient2D（pt1，center，pt2）; 
 
返回符号== 0？ 0：sign * acos（（aS + bS-cS）/（（sqrt（aS）* sqrt（bS）* 2）））; 
} 
 
 //计算一组点的平均点
 ii质心（vii& pts）
 {
 ii center（0， 0）; 
 for（int i = 0; i< pts.size（）; ++ i）
 {
 center.first + = pts [i] .first; 
 center.second + = pts [i] .second; 
} 
 
 center.first / = pts.size（）; 
 center.second / = pts.size（）; 
 
 return center; 
} 
 
 //使用单调链将一组点转换成一个凸包，逆时针顺序排列
 vii convexHull（vii& pts）
 { 
 sort（pts.begin（），pts.end（））; 
 vii up，dn; （up.size（）> 1&& orient2D（up）的
（int i = 0; i  {
 [up.size（） -  2]，up [up.size（） -  1]，pts [i]）> = 0）
 up.pop_back（）; （dn.size（））1&& orient2D（dn [dn.size（） -  2]，dn [dn.size（）-1]，pts [i]）≤b$ b， 0）
 dn.pop_back（）; 
 
 up.push_back（pts [i]）; 
 dn.push_back（pts [i]）; 
 
 
 for（int i = up.size（） -  2; i> 0; --i）
 {
 dn.push_back（up [一世]）; 
} 
 
 return dn; 
} 
 
 //测试一个点是否对多边形至关重要，即如果角度中心-qpt-polygon [i] 
 //比中心点更大（更小） qpt-polygon [i-1]和center-qpt-polygon [i + 1]。 
 //如果qpt-polygon [i] -polygon [i + 1]和qpt-polygon [i] -polygon [i-1] 
 //都是左转（min）或右转弯（最大）
 bool isCritical（vii& polygon，bool mx，int i，ii qpt，ii center）
 {
 int ip1 =（i + 1）％多边形。尺寸（）; 
 int im1 =（i + polygon.size（） -  1）％polygon.size（）; 
 
 int p1sign = orient2D（qpt，polygon [i]，polygon [ip1]）; 
 int m1sign = orient2D（qpt，polygon [i]，polygon [im1]）; 
 
 if（p1sign == 0&& m1sign == 0）
 {
 return false; 
} 
 
 if（mx）
 {
 return p1sign< = 0&& m1sign } 
 else 
 {
 return p1sign> = 0&& m1sign> = 0; 
} 
} 
 
 //在多边形上执行修改的二分查找以在O（log n）时间内查找切线。 
 //这相当于在旋转和离散的抛物线中查找最大值或最小值。 
 //香草二进制搜索不起作用，香草三元搜索也不行。但是，使用
 //只有一个最大值和最小值的事实，我们可以使用开始
 //和中点的点的斜率，以及它们在相互比较时的值，以确定在左侧或右侧部分中的最大值或最小值是否为
 // 
 bi find_tangent（vii& polygon，bool mx，ii qpt，int start，int end，ii center）
 {
 //当查询足够小时，迭代点。这避免了更复杂的代码处理不可能的情况，因为
 //长，因为左边和右边至少相隔一个点。这不会影响渐近运行时间。 
 if（end  -  start  {
 for（int i = start; i< end; ++ i）
 {
 if（ isCritical（polygon，mx，i，qpt，center））
 {
 return bi（true，i）; 
} 
} 
 
 return bi（false，-1）; 
} 
 
 int mid =（start + end）/ 2; 
 
 //使用modulo环绕多边形
 int startm1 =（start + polygon.size（） -  1）％polygon.size（）; 
 int midm1 =（mid + polygon.size（） -  1）％polygon.size（）; 
 
 //左右角度
 double startA =角度（中心，qpt，多边形[开始]）; 
 double midA =角度（中心，qpt，多边形[mid]）; 
 
 //减1个角度，确定斜率
 double startm1A =角度（中心，qpt，多边形[startm1]）; 
 double midm1A =角度（中心，qpt，多边形[midm1]）; 
 
 int startSign = abs（startm1A  -  startA）< EP？ 0：（startm1A< startA？1：-1）; 
 int midSign = abs（midm1A  -  midA）< EP？ 0：（midm1A< midA？1：-1）; 
 
 bool left = true; 
 //天真27种情况：左角和左角可以<，==或者> ;, 
 //斜率可以是 - ，0或者+，并且每个左边和左边都有斜率， 
 // 3 * 3 * 3 = 27.有些情况是不可能的，所以这里是剩下的18. 
 if（abs（startA  -  midA）< EP）
 {
 if（startSign == -1）
 {
 left =！mx; 
} 
 else 
 {
 left = mx; 
 
 
 else if（startA< midA）
 {
 if（startSign == 1）
 {
 if（midSign == 1）
 {
 left = false; 
} 
 else if（midSign == -1）
 {
 left = mx; 
} 
 else 
 {
 left = false; 
 
 
 else if（startSign == -1）
 {
 if（midSign == -1）
 {
 left = true; 
} 
 else if（midSign == 1）
 {
 left =！mx; 
} 
 else 
 {
 left = true; 
} 
} 
 else 
 {
 if（midSign == -1）
 {
 left = false; 
} 
 else 
 {
 left = true; 
 
 
 $ b else 
 
 if（startSign == 1）
 {
 if（midSign == 1）
 {
 left = true; 
} 
 else if（midSign == -1）
 {
 left = mx; 
} 
 else 
 {
 left = true; 
 
 
 else if（startSign == -1）
 {
 if（midSign == -1）
 {
 left = false; 
} 
 else if（midSign == 1）
 {
 left =！mx; 
} 
 else 
 {
 left = false; 
 
 
 else 
 
 if（midSign == 1）
 {
 left = true; 
} 
 else 
 {
 left = false; 
 
 
 
 $ b如果（左）
返回find_tangent（多边形，mx，qpt，start，mid + 1 ， 中央）; 
} 
 else 
 {
 return find_tangent（polygon，mx，qpt，mid，end，center）; 
} 
} 
 
 int main（）{
 int n，m; 
 cin>> n>>米; 
 
 vii rawPoints（n）; 
 for（int i = 0; i< n; ++ i）
 {
 cin>> rawPoints [i] .first>> rawPoints [I]。第二; 
} 
 
 vii polygon = convexHull（rawPoints）; 
套< ii>点（polygon.begin（），polygon.end（））; 
 ii center = centroid（polygon）; 
 
 for（int i = 0; i  {
 ii pt; 
 cin>> pt.first>> pt.second; 
 
 bi top = find_tangent（polygon，true，pt，0，polygon.size（），center）; 
 bi bot = find_tangent（polygon，false，pt，0，polygon.size（），center）; 
 
 //如果查询点与其最大（顶部）和最小（bot）角点共线，则它是一个多边形点，或者如果没有任何点是关键点
 if（！top.first || orient2D（polygon [top.second]，pt，polygon [bot.second]）== 0 || points.count（pt））
 {
 cout< b ;< INSIDE<< ENDL; 
} 
 else 
 {
 cout<<多边形[top.second] .first<< <<多边形[top.second] .second<< <<多边形[bot.second] .first<< <<多边形[bot.second] .second<< ENDL; 
} 
} 
} 
  

我的怀疑是有问题使用角度函数。我缩小了它或者 find_tangent 。我在角度从 double 切换为 long long 时看到了g ++中的不同结果函数。 double 结果更接近正确，但我不明白为什么它应该有任何不同。我输入的值很小，没有溢出/舍入应该引起问题。当我分配给double时，我也看到了在执行 pow（x，2）或 x * x 时的不同之处。我不明白为什么这会有所作为。

任何帮助将不胜感激！

编辑：以下是输入文件：

以下是正确的结果：

以下是不正确的结果：

解决方案

问题出在这段代码上：

  //计算se的平均值（vii& pts）
 {
 ii center（0LL，0LL）; 
 for（int i = 0; i< pts.size（）; ++ i）
 {
 center.first + = pts [i] .first; 
 center.second + = pts [i] .second; 
} 
 
 center.first / = pts.size（）; //就在这儿！！ 
 center.second / = pts.size（）; 
 
 return center; 
} 
  

我不知道为什么，但是g ++取消了 center.first ，并将其转换为正整数，并用无符号整数除以 pts.size时溢出的 long long 。通过将语句转换为：

  center.first / =（long long）pts.size（）; 
 center.second / =（long long）pts.size（）; 
  

g ++和VS c ++的输出匹配。

I have a program that works in VS C++ and does not work with g++. Here is the code:

#define _USE_MATH_DEFINES

#include <cmath>
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <set>

#define EP 1e-10

using namespace std;

typedef pair<long long, long long> ii;
typedef pair<bool, int> bi;
typedef vector<ii> vii;

// Returns the orientation of three points in 2D space
int orient2D(ii pt0, ii pt1, ii pt2)
{
    long long result = (pt1.first - pt0.first)*(pt2.second - pt0.second) 
        - (pt1.second - pt0.second)*(pt2.first - pt0.first);
    return result == 0 ? 0 : result < 0 ? -1 : 1;
}

// Returns the angle derived from law of cosines center-pt1-pt2.
// Defined to be negative if pt2 is to the right of segment pt1 to center
double angle(ii center, ii pt1, ii pt2)
{
    double aS = pow(center.first - pt1.first, 2) + pow(center.second - pt1.second, 2);
    double bS = pow(pt2.first - pt1.first, 2) + pow(pt2.second - pt1.second, 2);
    double cS = pow(center.first - pt2.first, 2) + pow(center.second - pt2.second, 2);

/*  long long aS = (center.first - pt1.first)*(center.first - pt1.first) + (center.second - pt1.second)*(center.second - pt1.second);
    long long bS = (pt2.first - pt1.first)*(pt2.first - pt1.first) + (pt2.second - pt1.second)*(pt2.second - pt1.second);
    long long cS = (center.first - pt2.first)*(center.first - pt2.first) + (center.second - pt2.second)*(center.second - pt2.second);*/

    int sign = orient2D(pt1, center, pt2);

    return sign == 0 ? 0 : sign * acos((aS + bS - cS) / ((sqrt(aS) * sqrt(bS) * 2)));
}

// Computes the average point of the set of points
ii centroid(vii &pts)
{
    ii center(0, 0);
    for (int i = 0; i < pts.size(); ++i)
    {
        center.first += pts[i].first;
        center.second += pts[i].second;
    }

    center.first /= pts.size();
    center.second /= pts.size();

    return center;
}

// Uses monotone chain to convert a set of points into a convex hull, ordered counter-clockwise
vii convexHull(vii &pts)
{
    sort(pts.begin(), pts.end());
    vii up, dn;
    for (int i = 0; i < pts.size(); ++i)
    {
        while (up.size() > 1 && orient2D(up[up.size()-2], up[up.size()-1], pts[i]) >= 0)
            up.pop_back();
        while (dn.size() > 1 && orient2D(dn[dn.size()-2], dn[dn.size()-1], pts[i]) <= 0)
            dn.pop_back();

        up.push_back(pts[i]);
        dn.push_back(pts[i]);
    }

    for (int i = up.size()-2; i > 0; --i)
    {
        dn.push_back(up[i]);
    }

    return dn;
}

// Tests if a point is critical on the polygon, i.e. if angle center-qpt-polygon[i]
// is larger (smaller) than center-qpt-polygon[i-1] and center-qpt-polygon[i+1].
// This is true iff qpt-polygon[i]-polygon[i+1] and qpt-polygon[i]-polygon[i-1]
// are both left turns (min) or right turns (max)
bool isCritical(vii &polygon, bool mx, int i, ii qpt, ii center)
{
    int ip1 = (i + 1) % polygon.size();
    int im1 = (i + polygon.size() - 1) % polygon.size();

    int p1sign = orient2D(qpt, polygon[i], polygon[ip1]);
    int m1sign = orient2D(qpt, polygon[i], polygon[im1]);

    if (p1sign == 0 && m1sign == 0)
    {
        return false;
    }

    if (mx)
    {
        return p1sign <= 0 && m1sign <= 0;
    }
    else
    {
        return p1sign >= 0 && m1sign >= 0;
    }
}

// Conducts modified binary search on the polygon to find tangent lines in O(log n) time.
// This is equivalent to finding a max or min in a "parabola" that is rotated and discrete.
// Vanilla binary search does not work and neither does vanilla ternary search. However, using
// the fact that there is only a single max and min, we can use the slopes of the points at start
// and mid, as well as their values when compared to each other, to determine if the max or min is
// in the left or right section
bi find_tangent(vii &polygon, bool mx, ii qpt, int start, int end, ii center)
{
    // When query is small enough, iterate the points. This avoids more complicated code dealing with the cases not possible as
    // long as left and right are at least one point apart. This does not affect the asymptotic runtime.
    if (end - start <= 4)
    {
        for (int i = start; i < end; ++i)
        {
            if (isCritical(polygon, mx, i, qpt, center))
            {
                return bi(true, i);
            }
        }

        return bi(false, -1);
    }

    int mid = (start + end) / 2;

    // use modulo to wrap around the polygon
    int startm1 = (start + polygon.size() - 1) % polygon.size();
    int midm1 = (mid + polygon.size() - 1) % polygon.size();

    // left and right angles
    double startA = angle(center, qpt, polygon[start]);
    double midA = angle(center, qpt, polygon[mid]);

    // minus 1 angles, to determine slope
    double startm1A = angle(center, qpt, polygon[startm1]);
    double midm1A = angle(center, qpt, polygon[midm1]);

    int startSign = abs(startm1A - startA) < EP ? 0 : (startm1A < startA ? 1 : -1);
    int midSign = abs(midm1A - midA) < EP ? 0 : (midm1A < midA ? 1 : -1);

    bool left = true;
    // naively 27 cases: left and left angles can be <, ==, or >,
    // slopes can be -, 0, or +, and each left and left has slopes,
    // 3 * 3 * 3 = 27. Some cases are impossible, so here are the remaining 18.
    if (abs(startA - midA) < EP)
    {
        if (startSign == -1)
        {
            left = !mx;
        }
        else
        {
            left = mx;
        }
    }
    else if (startA < midA)
    {
        if (startSign == 1)
        {
            if (midSign == 1)
            {
                left = false;
            }
            else if (midSign == -1)
            {
                left = mx;
            }
            else
            {
                left = false;
            }
        }
        else if (startSign == -1)
        {
            if (midSign == -1)
            {
                left = true;
            }
            else if (midSign == 1)
            {
                left = !mx;
            }
            else
            {
                left = true;
            }
        }
        else
        {
            if (midSign == -1)
            {
                left = false;
            }
            else
            {
                left = true;
            }
        }
    }
    else
    {
        if (startSign == 1)
        {
            if (midSign == 1)
            {
                left = true;
            }
            else if (midSign == -1)
            {
                left = mx;
            }
            else
            {
                left = true;
            }
        }
        else if (startSign == -1)
        {
            if (midSign == -1)
            {
                left = false;
            }
            else if (midSign == 1)
            {
                left = !mx;
            }
            else
            {
                left = false;
            }
        }
        else
        {
            if (midSign == 1)
            {
                left = true;
            }
            else
            {
                left = false;
            }
        }
    }

    if (left)
    {
        return find_tangent(polygon, mx, qpt, start, mid+1, center);
    }
    else
    {
        return find_tangent(polygon, mx, qpt, mid, end, center);
    }
}

int main(){
    int n, m;
    cin >> n >> m;

    vii rawPoints(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> rawPoints[i].first >> rawPoints[i].second;
    }

    vii polygon = convexHull(rawPoints);
    set<ii> points(polygon.begin(), polygon.end());
    ii center = centroid(polygon);

    for (int i = 0; i < m; ++i)
    {
        ii pt;
        cin >> pt.first >> pt.second;

        bi top = find_tangent(polygon, true, pt, 0, polygon.size(), center);
        bi bot = find_tangent(polygon, false, pt, 0, polygon.size(), center);

        // a query point is inside if it is collinear with its max (top) and min (bot) angled points, it is a polygon point, or if none of the points are critical
        if (!top.first || orient2D(polygon[top.second], pt, polygon[bot.second]) == 0 || points.count(pt))
        {
            cout << "INSIDE" << endl;
        }
        else
        {
            cout << polygon[top.second].first << " " << polygon[top.second].second << " " << polygon[bot.second].first << " " << polygon[bot.second].second << endl;
        }
    }
}

My suspicion is there's something wrong with the angle function. I have narrowed it down to either that or find_tangent. I also see different results in g++ when I switch from double to long long in the angle function. The double results are closer to correct, but I can't see why it should be any different. The values I'm feeding in are small and no overflow/ rounding should be causing issues. I have also seen differences in doing pow(x, 2) or x*x when I assign to a double. I don't understand why this would make a difference.

Any help would be appreciated!

EDIT: Here is the input file: https://github.com/brycesandlund/Coursework/blob/master/Java/PrintPoints/points.txt

Here is the correct result:https://github.com/brycesandlund/Coursework/blob/master/CompGeo/CompGeo/correct.txt

Here is the incorrect result:https://github.com/brycesandlund/Coursework/blob/master/CompGeo/CompGeo/fast.txt

解决方案

The problem was with this piece of code:

// Computes the average point of the set of points
ii centroid(vii &pts)
{
    ii center(0LL, 0LL);
    for (int i = 0; i < pts.size(); ++i)
    {
        center.first += pts[i].first;
        center.second += pts[i].second;
    }

    center.first /= pts.size();     //right here!!
    center.second /= pts.size();

    return center;
}

I don't know why but g++ was taking the negative center.first and turning it into a positive, overflowed long long when dividing by the unsigned integer pts.size. By converting the statements into:

center.first /= (long long)pts.size();
center.second /= (long long)pts.size();

The output from g++ and VS c++ matches.

这篇关于不同的结果VS C ++和GNU g ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！