# 挑战程序竞赛系列（92）：3.6凸包（3）

## 挑战程序竞赛系列（92）：3.6凸包（3）

```import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{

String INPUT = "./data/judge/201709/P1912.txt";

public static void main(String[] args) throws IOException {
new Main().run();
}

static final int MAX_N = 100000 + 16;
static final double EPS = 1E-10;
static final double PI  = Math.acos(-1.0);

class P implements Comparable<P>{

double x;
double y;

P (double x, double y){
this.x = x;
this.y = y;
}

double add(double a, double b) {
if (Math.abs(a + b) < EPS * (Math.abs(a) + Math.abs(b))) return 0;
return a + b;
}

}

P sub(P a) {
}

double dot(P a) {
return a.x * x + a.y * y;
}

double det(P a) {
return x * a.y - y * a.x;
}

@Override
public int compareTo(P o) {
int cmp = Double.compare(x, o.x);
return cmp != 0 ? cmp : Double.compare(y, o.y);
}
}

int N;
P[] ps;

P[] convexHull() {
Arrays.sort(ps);
if (N <= 1) return ps;

P[] qs = new P[N * 2];
int k = 0;
for (int i = 0; i < N; qs[k++] = ps[i++]) {
while (k > 1 && qs[k - 1].sub(qs[k - 2]).det(ps[i].sub(qs[k - 1])) < EPS) k--;
}

for (int i = N - 2, t = k; i >= 0; qs[k++] = ps[i--]) {
while (k > t && qs[k - 1].sub(qs[k - 2]).det(ps[i].sub(qs[k - 1])) < EPS) k--;
}

P[] res = new P[k - 1];
System.arraycopy(qs, 0, res, 0, k - 1);
return res;
}

double angle(P a, P b) {
P t = b.sub(a);
double ang = Math.atan2(t.y, t.x);
if (ang < -PI / 2 + EPS) ang += 2 * PI;
return ang;
}

int lowerBound(double[] ds, double v) {
int l = 0, r = ds.length;
while (l < r) {
int m = (r + l) >> 1;
if (ds[m] < v) l = m + 1;
else r = m;
}
return l;
}

//a, b是否在直线st的两侧
boolean check(P a, P b, P s, P t) {
return a.sub(s).det(t.sub(s)) * b.sub(s).det(t.sub(s)) <= 0;
}

boolean cross(P[] qs, double[] ds, P p1, P p2) {
int i = lowerBound(ds, angle(p1, p2));
int j = lowerBound(ds, angle(p2, p1));
i %= qs.length;
j %= qs.length;

return check(qs[i], qs[j], p1, p2);
}

void solve() {

P[] qs = convexHull();
int n = qs.length;
double[] ds = new double[n];

for (int i = 0; i < n; ++i) {
ds[i] = angle(qs[i], qs[(i + 1) % n]);
}

while (more()) {
P p1 = new P(nd(), nd());
P p2 = new P(nd(), nd());
if (N <= 1 || !cross(qs, ds, p1, p2)) out.println("GOOD");
}
}

N = ni();
ps = new P[N];
for (int i = 0; i < N; ++i) {
ps[i] = new P(nd(), nd());
}
solve();
}

FastScanner in;
PrintWriter out;

void run() throws IOException {
boolean oj;
try {
oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
} catch (Exception e) {
oj = System.getProperty("ONLINE_JUDGE") != null;
}

InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
in = new FastScanner(is);
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
out.flush();
if (!oj){
System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
}
}

public boolean more(){
return in.hasNext();
}

public int ni(){
return in.nextInt();
}

public long nl(){
return in.nextLong();
}

public double nd(){
return in.nextDouble();
}

public String ns(){
return in.nextString();
}

public char nc(){
return in.nextChar();
}

class FastScanner {
StringTokenizer st;
boolean hasNext;

public FastScanner(InputStream is) throws IOException {
hasNext = true;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
} catch (Exception e) {
hasNext = false;
return "##";
}
}
return st.nextToken();
}

String next = null;
public boolean hasNext(){
next = nextToken();
return hasNext;
}

public int nextInt() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Integer.parseInt(more);
}

public long nextLong() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Long.parseLong(more);
}

public double nextDouble() {
if (next == null){
hasNext();
}
String more = next;
next = null;
return Double.parseDouble(more);
}

public String nextString(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more;
}

public char nextChar(){
if (next == null){
hasNext();
}
String more = next;
next = null;
return more.charAt(0);
}
}
}```

98 篇文章33 人订阅

0 条评论

## 相关文章

852

3626

### poj-1056-IMMEDIATE DECODABILITY（字典）

An encoding of a set of symbols is said to be immediately decodable if no code f...

801

3568

2313

973

### 讨厌算法的程序员 6 - 归并排序

? 分而治之 分而治之 从算法设计的分类上来说，插入排序属于增量方法。在排序好子数组A[1 ‥ j-1]后，再将单个元素A[j]插入子数组的适当位置，产生排序...

2564

963

3445

### 【算法】希尔排序学习笔记

【参考资料】 《算法（第4版）》         — — Robert Sedgewick， Kevin Wayne 在本篇笔记里，我从简单的插入排序，到希尔排...

2098