Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Here is a more intuitive explanation for E. Sorry if it's mentioned already.
- Fix the point p. Translate everything such that p coincides with the origin. Sort all the other points counter-clockwise. We shall now find the number of quadruples of points that don't form a polygon containing p.
- Now consider some point s. Consider the half-plane H of points t such that the cross product s∧t is positive. For a quadrilateral with s to contain p, it has to have at least one point from H and at least one point not from H. Conversely, we will count the number of quadruples (s,t1,t2,t3) such that t1,t2,t3∈H. It is just the binomial coefficient (|H|3).
- Now do that for all s and all corresponding H, in linear time, using the two pointers method.
- With iterating over all p and sorting, the complexity is O(n2logn).
- I'll put it short:
- (By kdh9949 jihoon) Find f(p) for each point. You can see that the set can enclose p iff its convex hull contains p. Checking the containment is hard, so sort by angle, and eliminate the set that does not contain p, which reduces to almost similar sweep with model code. I think this is the easiest solution to come up with.
- (By molamola.) The answer depends on the 2 * (number of convex quadrilaterals) + (number of concave quadrilaterals). We denote this number A. I think the answer is (A−2(n4))×(n−4)/2, or something like that. This problem is bit harder, so you need another type of angular sweep like JOI Open 2017 Bulldozer. I think this is more involved to code, but our great tester molamola. took exactly 12 minutes to AC this.
- ll ans;
- pi pos[2505];
- int main() {
- setIO();
- int n;
- cin >> n;
- for(int i = 1; i <= n; i++){
- cin >> pos[i].f >> pos[i].s;
- }
- for(int i = 1; i <= n; i++){
- vector<P> angles;
- for(int j = 1; j <= n; j++){
- if(i == j) continue;
- P trans = mp(pos[j].f-pos[i].f, pos[j].s-pos[i].s);
- angles.pb(trans);
- }
- sort(all(angles), angleCmp);
- ll curnum = 0;
- int r = 0;
- ll m = ll(sz(angles));
- for(int i = 0; i < m; i++){
- //we need to find number of points between theta, theta+PI
- if(i == r+1) r++;
- while(true){
- P nexpossible = angles[(r+1) % sz(angles)];
- if(cross(angles[i], nexpossible) > 0){
- r++;
- }
- else break;
- }
- int num;
- if(r-i >= 0) num = r-i;
- else num = r+n-i;
- curnum+=(ll(num)*(ll(num)-1)*(ll(num)-2))/6;
- }
- curnum = (m*(m-1)*(m-2)*(m-3))/24-curnum;
- ans+=curnum;
- }
- ps(ans);
- }
- struct P{
- int x,y;
- P(){}
- P(int _x,int _y){
- x=_x; y=_y;
- }
- P operator -(const P &a)const{
- return P(x-a.x,y-a.y);
- }
- ll operator *(const P &a)const{
- return 1ll*x*a.y-1ll*y*a.x;
- }
- }a[5005],b[5005];
- int top,n;
- ll ans;
- bool in(P a){
- if (a.x) return a.x>0;
- return a.y>0;
- }
- bool cmp(P a,P b){
- if (in(a)!=in(b)) return in(a);
- return a*b>0;
- }
- void Func(int id){
- int top=0;
- For(i,1,n) if (i!=id) b[++top]=a[i]-a[id];
- ans+=1ll*(n-1)*(n-2)*(n-3)*(n-4)/24;
- //printf("%d\n",ans);
- sort(b+1,b+top+1,cmp);
- For(i,1,top) b[i+top]=b[i];
- int p=0;
- For(i,1,top){
- p=max(p,i);
- for (;p<i+top&&b[i]*b[p]>=0;++p);
- //printf("%d %d\n",i,p);
- ans-=1ll*(p-i-1)*(p-i-2)*(p-i-3)/6;
- }
- }
- int main(){
- scanf("%d",&n);
- For(i,1,n) scanf("%d%d",&a[i].x,&a[i].y);
- For(i,1,n) Func(i);
- printf("%lld\n",ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement