這個(gè)題我是按照discussion里面的說法，先求凸包，然后枚舉過的。因?yàn)殚_始先把求凸包算法里面的用到了數(shù)組名搞混了，無故wa了好
多次。后面求凸包換了種算法過了。結(jié)果發(fā)現(xiàn)bug是搞混了數(shù)組名，然后把前面wa掉的代碼下載下來，改好之后也都過了。
這個(gè)題主要是凸包算法需要處理有重復(fù)點(diǎn)，有多點(diǎn)共線之類的情況。那個(gè)按極角排序后，再求凸包的算法，對(duì)共點(diǎn)共線處理的不是很好，
不過那個(gè)算法也過了這個(gè)題。有個(gè)直接按坐標(biāo)排序后，再求上凸包和下凸包的算法，可以處理共點(diǎn)共線的情況。這個(gè)算法比較優(yōu)美啊，既不
需要找y坐標(biāo)最小的點(diǎn)，也不需要按極角排序，直接按坐標(biāo)排序下，然后求凸包即可。
這個(gè)算法的一點(diǎn)解釋：
http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull 另外，演算法筆記：
http://www.csie.ntnu.edu.tw/~u91029/ConvexHull.html#a3上也有提到這個(gè)算法，我也是從這上面看到的。
這個(gè)算法可以假設(shè)是Graham排序基準(zhǔn)點(diǎn)在無限遠(yuǎn)處，于是夾角大小的比較可以直接按水平坐標(biāo)比較。
代碼如下：
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct Point
{
int x, y;
bool operator<(
const Point& p)
const {
return x < p.x || x == p.x && y < p.y;
}
};
Point pts[50100];
Point pcs[50100];
int nN;
int nM;
inline
int SDis(
const Point& a,
const Point& b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double Det(
double fX1,
double fY1,
double fX2,
double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
void Convex()
{
sort(pts, pts + nN);
nM = 0;
for (
int i = 0; i < nN; ++i)
{
while(nM >= 2 && Cross(pcs[nM - 2], pcs[nM - 1], pts[i]) <= 0)
{
nM--;
}
pcs[nM++] = pts[i];
}
for (
int i= nN - 2, t = nM + 1; i >= 0; --i)
{
while (nM >= t && Cross(pcs[nM - 2], pcs[nM - 1], pts[i]) <= 0)
{
nM--;
}
pcs[nM++] = pts[i];
}
nM--;
//起點(diǎn)會(huì)被重復(fù)包含
}
int main()
{
while (scanf("%d", &nN) == 1)
{
for (
int i = 0; i < nN; ++i)
{
scanf("%d%d", &pts[i].x, &pts[i].y);
}
Convex();
int nMax = -1;
for (
int i = 0; i < nM; ++i)
{
for (
int j = i + 1; j < nM; ++j)
{
nMax = max(nMax, SDis(pcs[i], pcs[j]));
}
}
printf("%d\n", nMax);
}
return 0;
}
也可以用旋轉(zhuǎn)卡殼算法來求最遠(yuǎn)點(diǎn)對(duì)，此題的完整代碼如下：
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
struct Point
{
int x, y;
bool operator<(const Point& p) const
{
return x < p.x || x == p.x && y < p.y;
}
};
Point pts[50100];
Point pcs[50100];
int nN;
int nM;
inline int SDis(const Point& a, const Point& b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
double Det(double fX1, double fY1, double fX2, double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
void Convex()
{
sort(pts, pts + nN);
nM = 0;
for (int i = 0; i < nN; ++i)
{
while(nM >= 2 && Cross(pcs[nM - 2], pcs[nM - 1], pts[i]) <= 0)
{
nM--;
}
pcs[nM++] = pts[i];
}
for (int i= nN - 2, t = nM + 1; i >= 0; --i)
{
while (nM >= t && Cross(pcs[nM - 2], pcs[nM - 1], pts[i]) <= 0)
{
nM--;
}
pcs[nM++] = pts[i];
}
nM--;//起點(diǎn)會(huì)被重復(fù)包含
}
int main()
{
while (scanf("%d", &nN) == 1)
{
for (int i = 0; i < nN; ++i)
{
scanf("%d%d", &pts[i].x, &pts[i].y);
}
Convex();
int nMax = -1;
for (int i = 0; i < nM; ++i)
{
for (int j = i + 1; j < nM; ++j)
{
nMax = max(nMax, SDis(pcs[i], pcs[j]));
}
}
printf("%d\n", nMax);
}
return 0;
#include <stdio.h>
#include <
string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Point
{
int x, y;
bool operator < (
const Point& p)
const {
return x < p.x || x == p.x && y < p.y;
}
};
double Det(
double fX1,
double fY1,
double fX2,
double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
//輸入點(diǎn)集合,輸出凸包
void Convex(vector<Point>&
in, vector<Point>&
out)
{
int nN =
in.size();
int nM = 0;
sort(
in.begin(),
in.end());
out.resize(nN);
for (
int i = 0; i < nN; ++i)
{
while (nM >= 2 && Cross(
out[nM - 2],
out[nM - 1],
in[i]) <= 0)
{
nM--;
}
out[nM++] =
in[i];
}
for (
int i = nN - 2, t = nM + 1; i >= 0; --i)
{
while (nM >= t && Cross(
out[nM - 2],
out[nM - 1],
in[i]) <= 0)
{
nM--;
}
out[nM++] =
in[i];
}
out.resize(nM);
out.pop_back();
//起始點(diǎn)重復(fù)
}
int SDis(Point a,Point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int RC(vector<Point>& vp)
{
int nP = 1;
int nN = vp.size();
vp.push_back(vp[0]);
int nAns = 0;
for (
int i = 0; i < nN; ++i)
{
while (Cross(vp[i], vp[i + 1], vp[nP + 1]) > Cross(vp[i], vp[i + 1], vp[nP]))
{
nP = (nP + 1) % nN;
}
nAns = max(nAns, max(SDis(vp[i], vp[nP]), SDis(vp[i + 1], vp[nP + 1])));
}
vp.pop_back();
return nAns;
}
int main()
{
int nN;
vector<Point>
in,
out;
Point p;
while (scanf("%d", &nN) == 1)
{
in.clear(),
out.clear();
while (nN--)
{
scanf("%d%d", &p.x, &p.y);
in.push_back(p);
}
Convex(
in,
out);
printf("%d\n", RC(
out));
}
return 0;
}
關(guān)于旋轉(zhuǎn)卡殼的算法描述，網(wǎng)上有很多資料，比如，
http://www.shnenglu.com/staryjy/archive/2010/09/25/101412.html 尤其關(guān)于這個(gè)求最遠(yuǎn)點(diǎn)對(duì)的。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
struct Point
{
int x, y;
bool operator < (const Point& p)const
{
return x < p.x || x == p.x && y < p.y;
}
};
double Det(double fX1, double fY1, double fX2, double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
//輸入點(diǎn)集合,輸出凸包
void Convex(vector<Point>& in, vector<Point>& out)
{
int nN = in.size();
int nM = 0;
sort(in.begin(), in.end());
out.resize(nN);
for (int i = 0; i < nN; ++i)
{
while (nM >= 2 && Cross(out[nM - 2], out[nM - 1], in[i]) <= 0)
{
nM--;
}
out[nM++] = in[i];
}
for (int i = nN - 2, t = nM + 1; i >= 0; --i)
{
while (nM >= t && Cross(out[nM - 2], out[nM - 1], in[i]) <= 0)
{
nM--;
}
out[nM++] = in[i];
}
out.resize(nM);
out.pop_back();//起始點(diǎn)重復(fù)
}
int SDis(Point a,Point b)
{
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int RC(vector<Point>& vp)
{
int nP = 1;
int nN = vp.size();
vp.push_back(vp[0]);
int nAns = 0;
for (int i = 0; i < nN; ++i)
{
while (Cross(vp[i], vp[i + 1], vp[nP + 1]) > Cross(vp[i], vp[i + 1], vp[nP]))
{
nP = (nP + 1) % nN;
}
nAns = max(nAns, max(SDis(vp[i], vp[nP]), SDis(vp[i + 1], vp[nP + 1])));
}
vp.pop_back();
return nAns;
}
int main()
{
int nN;
vector<Point> in, out;
Point p;
while (scanf("%d", &nN) == 1)
{
in.clear(), out.clear();
while (nN--)
{
scanf("%d%d", &p.x, &p.y);
in.push_back(p);
}
Convex(in, out);
printf("%d\n", RC(out));
}
return 0;
}