2020牛客暑假多校B Boundary（计算几何） G Greater and Greater（bitset）

题意给出n个点（2e3），问构造一个圆形，使得通过远点，边缘上的点数最多。

 

 

先说我自己的做法吧，一开始用的三点共圆，但是考虑到时间复杂度太大，因为当时傻逼了，没考虑到n*n/2，这样就成2e6加个map了（但是当时傻逼了以为用个二维map肯定没啊），当时感觉这样肯定T了，但没想到map +pair可以过的（牛客评测机跑得就是快啊）。然后就去写垂直平分线的了，因为两条垂直平分线的交点一定可以确定一个圆心，其实思路也一样，同样是确定圆心，就是把map写成排序了，但多加了一倍的复杂度，因为如果是1，2，3，同在圆心上，那么 （1，2）（1，3）（2，1）（2，3）（3，1）（3，2） 都算上了，所以最后结果要除个根号，这里饶了几圈，最后eps定义的是1e-10还卡掉了，赛后看到过了95，改成1e-6就过了，这是真的n*nlogn了

 

 

#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=a;i>=n;i--)
using namespace std;
const double epsi=1e-6;
const double eps=1e-6;
struct Point
{
    double x,y;
    Point(double _x=0,double _y=0):x(_x),y(_y){}
    Point operator -(const Point &op) const
    {
        return Point(x-op.x,y-op.y);
    }
    double operator ^(const Point &op) const
    {
        return x*op.y-y*op.x;
    }
};
inline int sign(const double &x)
{
    if(x>epsi) return 1;
    if(x<-epsi) return -1;
    return 0;
}
inline double sqr( const double &x)
{
    return x*x;
}
inline double dis(const Point &p1,const Point &p2)
{
    return sqrt(sqr(p1.x-p2.x)+sqr(p1.y-p2.y));
}
inline double mul(const Point &p0,const Point &p1,const Point &p2)
{
    return (p1-p0)^(p2-p0);
}
inline int cross(const Point &p1,const Point &p2,const Point &p3,const Point &p4,Point &p)
{
    double a1=mul(p1,p2,p3),a2=mul(p1,p2,p4);
    if(sign(a1)==0&&sign(a2)==0) return 2;//重叠
    if(sign(a1-a2)==0) return 0;//平行
    p.x=(a2*p3.x-a1*p4.x)/(a2-a1);
    p.y=(a2*p3.y-a1*p4.y)/(a2-a1);
    return 1;//相交
}
Point p1,p2,p3,p4,p;
int n,m;
double x[120000],y[120000];
double x2[120000],y2[120000];
map<double,int>mp;
struct stu
{
    double x,y;
}A[4200000];
double cmp(stu a,stu b)
{
    if(fabs(a.x-b.x)<eps)
    return a.y<b.y;
    return a.x<b.x;
}
  
int main()
{
    int test=0;
    //printf("INTERSECTING LINES OUTPUT\n");
    cin>>n;
//  double x,y;
    rep(i,1,n)
    {
        double xx,yy;
        scanf("%lf%lf",&xx,&yy);
        //0,0   x,y
        x[i]=(xx)/2;
        y[i]=(yy)/2;
        if(fabs(xx-0.0)<eps)
        {
            x2[i]=x[i]+10000.0;
            y2[i]=y[i];
        }
        else if(fabs(yy-0.0)<eps)
        {
            x2[i]=x[i];
            y2[i]=y[i]+10000.0;
        }
        else
        {
            double k=-xx/yy;
            double b=y[i]-k*x[i];
            x2[i]=0.0;
            y2[i]=b;
        }
        //printf("%lf  %lf  %lf  %lf  \n",x[i],y[i],x2[i],y2[i]);
    }
    int cnt=0;
    rep(i,1,n)
    {
        rep(j,1,n)
        {
            if(i!=j)
            {
                p1.x=x[i];p1.y=y[i];
                p2.x=x2[i];p2.y=y2[i];
                p3.x=x[j];p3.y=y[j];
                p4.x=x2[j];p4.y=y2[j];
                int fm=cross(p1,p2,p3,p4,p);
                if(fm==0) ;//printf("NONE\n");
                else if(fm==2) ;//printf("LINE\n");
                else
                {
                    //mp[p.x][p.y]++;
                //  printf("POINT %.2lf %.2lf\n",p.x,p.y);
                    A[++cnt].x=p.x;
                    A[cnt].y=p.y;
                }
            }
        }
    }
    sort(A+1,A+1+cnt,cmp);
    int k=1;
    int maxl=0,ans=1;
      
//  printf("dqwqwd\n");
    rep(i,1,cnt)
    {
        //printf("POINT %.2lf %.2lf\n",A[i].x,A[i].y);
    }
    rep(i,2,cnt)
    {
        if(   fabs(A[i].x-A[k].x)<eps  &&fabs(A[i].y-A[k].y)<eps )
        {
            ans++;
            maxl=max(maxl,ans);
        }
        else
        {
            ans=1;
            k=i;
        }
    }
    int p=sqrt(maxl);
    if(p<=1) p=1;
    maxl=maxl/p;
    if(maxl==0) maxl=1;
    cout<<maxl<<endl;
    return 0;
}

代码最短大佬的：（看了真的酸了）

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
const int maxn=2e3+9;
typedef pair<double,double> pdd;
int n;
double x[maxn],y[maxn];
map<pdd,int> res;
int main(){
    scanf("%d",&n);
    rep(i,0,n) scanf("%lf%lf",x+i,y+i);
    int ans=0;
    rep(i,0,n) {
        res.clear();
        rep(j,i+1,n){
            if(x[i]*y[j]==x[j]*y[i]) continue;
            double d=x[i]*y[j]-x[j]*y[i],d1=x[i]*x[i]+y[i]*y[i],d2=x[j]*x[j]+y[j]*y[j];
            double X=(y[i]*d2-y[j]*d1)/d,Y=(x[i]*d2-x[j]*d1)/d;
            ans=max(ans,++res[{X,Y}]);
        }
    }
    printf("%d\n",ans+1);
}

G：题意是给你两个数组，a：1e5+5e4，  b：4e4 

问a的长为b的连续子序列每个对应位置都>=b[i]的方案数。

然后朴素n*m谁都会，问题就在于如何优化跑，其实考虑到一段符合的解，如果右移一位的话，就是使得所有比较的数右移比较了，这样就可以用bitset优化了，然后考虑一个可行的方法，使a，b都按最大值递减排序，定义两个bitset，一个是ans也就是最终结果初始全制1（即为所有位置都满足条件），一个temp为b的空bitset

 

使a中数依次与b中数比较，因为一直都是递增下来排序的，所以每次对应位置我们就给对应的b的bitset制1，然后用ans&temp>>bi的下标（这个就是关键）其实这样算过之后就是对应位置对于b数组中前i的最大的都满足条件。最后ans的1的个数即为所求。确实是一个很典型的bitset，就是很难考虑到啊

//#pragma G++ optimize(2)
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef  long long ll;//unsigned
typedef unsigned long long ull;
char F[200];
inline bool read(ll &num){char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;};
inline void out(ll x){ if (x == 0) return (void) (putchar('0'));    ll tmp = x > 0 ? x : -x;    if (x < 0) putchar('-');    int cnt = 0;    while (tmp > 0) {        F[cnt++] = tmp % 10 + '0';        tmp /= 10;     }   while (cnt > 0) putchar(F[--cnt]);   printf("\n"); }
#define rep(i,a,n) for(ll i=a;i<=n;i++)
#define per(i,a,n) for(ll i=a;i>=n;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef pair<ll,ll> P;
const ll INF=5e18+7;const ll mod=998244353; const ll maxx=2e5+700;const double eps=1e-6;//const double pi=acos(-1);
ll gcd(ll a,ll b){  if(!b) return a;    return gcd(b,a%b);};
ll qpow(ll a,ll b){ll ans=1;    while(b)    {       if(b&1) ans=(ans*a)%mod;        a=a*a%mod;      b>>=1;    }   return ans;}
/*           */
//ll head[maxx];ll deep[maxx];ll vis[maxx];ll dis[maxx];map<ll,ll>mp;
ll dx[4]={-1,1,0,0};ll dy[4]={0,0,-1,1};//map<ll,ll>mp;//
vector<ll>v[maxx];queue<ll>q;
ll n,m; 
ll biaoji[maxx];
pair<ll,ll>pa[maxx];
pair<ll,ll>pb[maxx];
bitset<151000>temp,ans;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll k,p;
   	ll n;
   	cin>>n>>m;
   	rep(i,1,n)
   	{
   		cin>>pa[i].first;
   		pa[i].second=i;
	}
	rep(i,1,m)
	{
		cin>>pb[i].first;
		pb[i].second=i;
	}
	sort(pa+1,pa+1+n,greater<P>());
    sort(pb+1,pb+1+m,greater<P>());
	ans.set();  // 1
	for(int i=1,p=1;i<=m;i++)
    {
        while(p<=n&&pa[p].first>=pb[i].first)
        {
            temp[pa[p].second]=1;
            p++;
        }
        ans&=temp>>pb[i].second;  
        //cout<<ans<<endl;
        //cout<<temp<<endl;
    }
    cout<<ans.count()<<endl;
	return 0;
}