【POJ 1228】Grandpa's Estate 凸包

找到凸包后暴力枚举边进行$check$,注意凸包是一条线(或者说两条线)的情况要输出$NO$

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1003
#define read(x) x = getint()
using namespace std;
inline int getint() {
int k = 0, fh = 1; char c = getchar();
for(; c < '0' || c > '9'; c = getchar())
if (c == '-') fh = -1;
for(; c >= '0' && c <= '9'; c = getchar())
k = k * 10 + c - '0';
return k * fh;
}
struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
};
inline int dcmp(int x) {
return x == 0 ? 0 : (x < 0 ? -1 : 1);
}
Point operator - (Point a, Point b) {
return Point(a.x - b.x, a.y - b.y);
}
bool operator == (Point a, Point b) {
return a.x == b.x && a.y == b.y;
}
inline int Cross(Point a, Point b) {
return a.x * b.y - a.y * b.x;
}
inline int Dot(Point a, Point b) {
return a.x * b.x + a.y * b.y;
}
inline bool jiao(Point d1, Point d2, Point d3, Point d4) {
return (dcmp(Cross(d4 - d3, d1 - d3)) ^ dcmp(Cross(d4 - d3, d2 - d3)) == -2) &&
(dcmp(Cross(d2 - d1, d3 - d1)) ^ dcmp(Cross(d2 - d1, d4 - d1)) == -2);
}
inline bool onin(Point d1, Point d2, Point d3) {
return Cross(d2 - d1, d3 - d1) == 0 && Dot(d2 - d1, d3 - d1) < 0;
} Point a[N], tb[N];
int n, T, top; inline bool cmp(Point d1, Point d2) {
return d1.y == d2.y ? d1.x < d2.x : d1.y < d2.y;
}
inline void mktb() {
top = 2;
tb[1] = a[1];
tb[2] = a[2];
for(int i = 3; i <= n; ++i) {
while (Cross(a[i] - tb[top], tb[top] - tb[top - 1]) >= 0 && top > 1)
--top;
tb[++top] = a[i];
}
int k = top;
tb[++top] = a[n-1];
for(int i = n - 2; i >= 1; --i) {
while (Cross(a[i] - tb[top], tb[top] - tb[top - 1]) >= 0 && top > k)
--top;
tb[++top] = a[i];
}
}
inline bool check(Point d1, Point d2) {
for(int i = 1; i <= n; ++i)
if (onin(a[i], d1, d2))
return 1;
return 0;
}
int main() {
read(T);
while (T--) {
read(n);
for(int i = 1; i <= n; ++i)
read(a[i].x), read(a[i].y);
sort(a + 1, a + n + 1, cmp);
mktb(); bool pd = 1;
for(int i = 2; i <= top; ++i)
if (!check(tb[i], tb[i-1])) {
pd = 0;
break;
} (pd == 0 || top == 3) ? puts("NO") : puts("YES");
}
return 0;
}

这样就可以了

上一篇:【POJ】1228 Grandpa's Estate(凸包)


下一篇:linux command 2