Java 解法, 执行用时: 188ms, 内存消耗: 19852K, 提交时间: 2022-03-07 23:25:15

import java.io.*;
import java.util.*;
public class Main {
	static int []a = new int [1004];
	static int []b = new int [1003];
	static int n = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner (System.in);
		n = sc.nextInt();
		for (int i = 1 ; i <= n ; i++) {
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}
		int q = sc.nextInt();
		while (q-->0) {
			int x = sc.nextInt();
			int cont = 0;
			for (int i = 1 ; i <=n ; i++) {
				if (i != x && check(i,x)) cont++;
			}
			System.out.println(cont);
		}
	}
	
	static boolean check(int x , int y) {
		for (int i = 1 ; i <= n ; i++) {
			if (a[i] <= Math.min(a[x], a[y]) || a[i] >= Math.max(a[x], a[y])) continue;
			double h = (b[x]-b[y])*(a[i]-a[x])*1.0/(a[x]-a[y]) +b[x];
			if (b[i]>=h) return false;
		}
		return true;
	}
}

C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 396K, 提交时间: 2022-08-13 23:47:23

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n;
int pt(int x,int y){
    for(int i=1;i<=n;i++){
        if(a[i]<=min(a[x],a[y])||a[i]>=max(a[x],a[y]))continue;
        double h=(a[i]-a[x])*(b[y]-b[x])*1.0/(a[y]-a[x])+b[x];
        if(b[i]>=h)return 0;
    }
    return 1;
    
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i];
    int q;
    cin>>q;
    while(q--){
        int x;
        cin>>x;
        int cn=0;
        for(int i=1;i<=n;i++){
            if(x!=i&&pt(x,i))cn++;
        }
        cout<<cn<<endl;
    }
    
    
    return 0;
}

C++ 解法, 执行用时: 6ms, 内存消耗: 400K, 提交时间: 2021-12-02 14:49:31

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int n;
int pt(int x,int y)
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]<=min(a[x],a[y])||a[i]>=max(a[x],a[y]))
		continue;
		double h=(a[i]-a[x])*(b[y]-b[x])*1.0/(a[y]-a[x])+b[x];
		if(b[i]>=h)
		return 0;
	}
	return 1;
 } 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i]>>b[i];
	int q;
	cin>>q;
	while(q--)
	{
		int x;
		cin>>x;
		int cn=0;
		for(int i=1;i<=n;i++)
		{
			if(x!=i&&pt(x,i))
			cn++;
		}
		cout<<cn<<endl;
	}
	return 0;
}