不同的结果VS C ++和GNU g ++ [英] Different results VS C++ and GNU g++
本文介绍了不同的结果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 <= 0;
}
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 <= 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;
//使用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 时的不同之处。我不明白为什么这会有所作为。
任何帮助将不胜感激！
编辑：以下是输入文件： https://github.com/brycesandlund /Coursework/blob/master/Java/PrintPoints/points.txt
以下是正确的结果：
https://github.com/brycesandlund/Coursework/blob/master/CompGeo/CompGeo/correct。 txt
以下是不正确的结果：
https://github.com/brycesandlund/Coursework/blob/master/CompGeo/CompGeo/fast.txt
解决方案
问题出在这段代码上：
//计算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 ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
