Weekly test 5

describe

In two-dimensional plane, given n points {ai} and M points {bi}, it is guaranteed that the x coordinates or y coordinates of any two points in n+m points are different.

For each bi, the existence of a triangle consisting of three ai,aj,ak(1 < i,j,k < n,i J k) points containing Bi (also included on the edge of the triangle; a triangle with three collinear points is allowed, and only Bi is included on the line segment of any two points in the three points).

input

The first action is an integer n. Next, line n, where line i has two integers, representing the horizontal and vertical coordinates of ai.

The first action is an integer M. Next, line m, where line i has two integers, representing the horizontal and vertical coordinates of bi.

output

Output m lines, the i behavior of an integer 0 or 1, respectively, indicate whether there is a triangle containing the bi.

Sample 1 input

3 1 -6 -10 -1 0 6 3 -2 7 -4 -2 -3 1

Sample 1 output

0 1 1

Example 1 Interpretation

As shown in the figure, the green dot is A and the red dot is B. Red dots No. 2 and No. 3 are all contained in three green dots.

Example 2

See sample2_input.txt and sample2_output.txt and draw.py in the next file.

In order to facilitate debugging, I specially provided a draw.py file to draw point sets. You need to install python 3, and then

python3 -m pip install matplotlib

Final use

python3 draw.py

Run, copy the data in the question to get the picture. (You can redirect data, of course)

limit

n,m (> 3), coordinate absolute value no more than 109

30% of the data, n,m < 200;

Another 30% data, n,m < 2000;

The remaining 40% of the data, n,m < 300000.

Time: 3 sec

Space: 256 MB

Note that using Python classmates, OJ provides you with pypy to speed up, the source code does not need to change at all, just modify the first line to enjoy high-speed python.

To use pypy, you have to add (or use the IO template I gave you directly) to the first line.

python 2:

#!/usr/bin/env pypy

python 3:

#!/usr/bin/env pypy3

Tips

[Convex hull, you can refer to the code of "Convex hull" which is selected as the topic]

In order to help you complete the topic, we provide program templates that only contain input and output functions.

You can answer on the basis of these procedures, or not refer to them, depending on your actual situation, which has nothing to do with your score.

These programs can be downloaded from [here].

Method 1 Assistant Teaching Method:

1. Firstly, the upper and lower convex hulls are obtained, and then the two counter-clockwise directed edges e1 and e2 which intersect the upper and lower convex hulls with x=x0 are obtained by dichotomy (if they do not intersect, the red dots are not in the convex hulls).

2. Then determine whether the red dot (x0, y0) is on the left side of e1 and E 2 at the same time, if it is in the convex hull, otherwise it is not.

The time complexity is O((n+m)logn)

My method and code are as follows:

https://blog.csdn.net/qq_36782366/article/details/78161807

Here we explain the template for judging whether a point is in a convex hull: a point's complexity is O (logn) complexity.

It is to take one of the points, he and other points can form n-2 triangles, using dichotomy to judge the product of difference, to judge whether he is in the current triangle, or on the left side of the triangle, or on the right side of the triangle, or outside the triangle.

#include <vector> #include <stdio.h> #include <iostream> #include <cstdio> #include <algorithm> using namespace std; // ================= Code implementation begins================= struct ip { int x, y, i; ip(int x = 0, int y = 0) : x(x), y(y), i(0) { } //Initialization list with the above equation as class void ri(int _i) { scanf("%d%d", &x, &y); i = _i; } }; typedef ip iv; const int N = 300005; ip a[N], b[N], ch[N]; //a [] storage needs n pairs of points constituting convex hulls, and b [] storage needs to judge m pairs of points inside and outside. //convexhull,ch [] stores actual convex hull boundary points // Compare the x-axis first and then the y-axis bool operator < (const ip &a, const ip &b) { return a.x == b.x ? a.y < b.y : a.x < b.x; } // Overload minus sign, use a - b to calculate the vector subtracted by two points iv operator - (const ip &a, const ip &b) { return ip(a.x - b.x, a.y - b.y); } // The cross product of a and b is calculated by a * b. long long operator * (const iv &a, const iv &b) { return (long long)a.x * b.y - (long long)a.y * b.x; } int convex(ip *a, int n) { //Ascending order sort(a,a+n); // n = unique(a,a+n)-a; / / / If there are repetitive points in the title, they must be de-duplicated int m=0; //Finding the Lower Convex Hull for(int i=0; i<n; ++i){ for(; m>1 && ((ch[m-1]-ch[m-2])*(a[i]-ch[m-2])) < 0; --m); ch[m++] = a[i]; } //Finding Upper Convex Hull for(int i=n-2, t=m; i>=0; --i){ for(; m>t && ((ch[m-1]-ch[m-2])*(a[i]-ch[m-2])) < 0; --m); ch[m++] = a[i]; } return m-1 ; //Number of points whose return value is convex hull } //Here we explain the template to determine whether the point is in the convex hull: //That is to take one of the points, he and other points can form n-2 triangles, using dichotomy to judge the product of difference. //Judge whether he is in the current triangle, or on the left side of the triangle, or on the right side of the triangle, or outside the triangle. int check(ip b,int n){ int l=1,r=n-2,mid; while(l<=r) { mid=(l+r)>>1; long long a1=(ch[mid]-ch[0])*(b-ch[0]); //Cross product of CH0 - > chmid and CH0 - > b long long a2=(ch[mid+1]-ch[0])*(b-ch[0]);//Cross product of CH0 - > chmid + 1 and CH0 - > b if(a1>=0&&a2<=0) //That is to say, this point b is above or on the line of chmid, and below or on the line of chmid+1. { if((ch[mid+1]-ch[mid])*(b-ch[mid])>=0) //Cross product of chmid - > chmid + 1 and chmid - > b return true; //If the cross product is greater than or equal to 0 at this time, it means that point b is inside or on the boundary of the triangle. return false; //Conversely, the point is outside the triangle. } else if(a1<0) //If the point is below chmid, then the upper boundary is reduced to mid-1. { r=mid-1; //The end point of dichotomy needs attention! } else //If the point is above chmid+1, then pull down the lower boundary to mid+1 { l=mid+1; } } return false; } // Returns an array, representing the answer in turn vector<int> getAnswer(int n, ip *a, int m, ip *b) { vector<int> ans; int mm = convex(a, n); //m is the length of the ch [] array for(int i=0; i<m; i++){ int t=check(b[i],mm); ans.push_back(t); } return ans; } // ================= End of Code Implementation================= int main() { int n, m; scanf("%d", &n); ip x; for (int i = 0; i < n; ++i) a[i].ri(i + 1); scanf("%d", &m); for (int i = 0; i < m; ++i) b[i].ri(i + 1); vector<int> ans = getAnswer(n, a, m, b); for (int i = 0; i < m; ++i) printf("%d\n", ans[i]); return 0; }