Consider the following game about removing N straight line segments on the plane. The segments are numbered from 1 to N. The i-th segment connects points (0,?i) and (1,?pi), where the numbers p1,?p2,?...,?pN are a permutation of numbers from 1 to N. Your are also given N positive integers v1,?v2,?...,?vN. On each step, you can select any segment i which is not removed yet, pay vi dollars, and then remove the i-th segment and all segments intersecting with it. Note that you MUST remove all segments which intersect with i-th segment.
The purpose of this game is to remove all segments while spending the minimum possible sum of dollars. Please answer how much you need to spend when you play the game with best strategy.
The input consists of three lines. The first line contains an integer N. The second line consists of N integers p1,?p2,?...,?pN. The third line consists of N integer v1,?v2,?...,?vN.
- 1?≤?N?≤?105
- is a permutation of 1,?2,?...,?N
- 1?≤?vi?≤?2?×?104
Output only one number indicating the minimum possible sum of dollars required to remove all segments.
4 2 1 4 3 1 2 3 4
4
4 1 2 3 4 1 2 3 4
10
计算几何+思路~
我们把所有点极角排序一遍，然后扫描计算每个角对于答案的贡献。
数组又双叒叕开小了，我是不是也应该像柴神那样写个副标题了2333
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long longint n,ans,b[100001],t,x;struct node{int x,y;
}a[100002];node operator - (node u,node v)
{return (node){u.x-v.x,u.y-v.y};
}ll operator * (node u,node v)
{return (ll)u.x*v.y-(ll)u.y*v.x;
}bool cmp(int u,int v)
{return a[u]*a[v]>0;
}int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}int main()
{n=read();for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(),b[i]=i;sort(b+1,b+n+1,cmp);a[0]=a[n];a[n+1]=a[1];for(int i=1,j=1;i<=n;i=j){x=0;for(j=i;j<=n && a[b[i]]*a[b[j]]==0;j++)if(a[b[j]]*a[b[j]-1]<=0 && a[b[j]]*a[b[j]+1]<0){if((a[b[j]-1]-a[b[j]])*(a[b[j]+1]-a[b[j]])<0) t--;else x--;}else if(a[b[j]]*a[b[j]-1]>0 && a[b[j]]*a[b[j]+1]>=0){if((a[b[j]-1]-a[b[j]])*(a[b[j]+1]-a[b[j]])>0) t++;else x++;}ans=max(ans,t);t+=x;ans=max(ans,t);}printf("%d\n",ans+1);return 0;
}
