哪位大佬帮我看看这个代码为什么错了

#include<bits/stdc++.h>
#define mems(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int mod=1e9+7,N=305;
struct vec
{
    ll x,y;int id;
    vec(ll x=0,ll y=0):x(x),y(y){}
    bool operator==(const vec&o)const{return x==o.x&&y==o.y;}
    vec operator+(const vec&o)const{ return vec(x+o.x,y+o.y);}
    vec operator-(const vec&o)const{ return vec(x-o.x,y-o.y);}
    ll operator*(const vec&o)const{ return x*o.x+y*o.y;}
    ll operator^(const vec&o)const{ return x*o.y-y*o.x;}
    vec operator/(const ll&o)const{ return vec(x/o,y/o);}
    vec operator*(const ll&o)const{ return vec(x*o,y*o);}
    void sc(){scanf("%lld%lld",&x,&y);}
    ll len(){return x*x+y*y;}
}a[N],b[N],c[N],s,t;
int n,t1,t2,le[N],ri[N];
bool cmp1(vec a,vec b)
{
    return ((a-s)^(b-s))>0;
}
bool cmp2(vec a,vec b)
{
    return ((a-s)^(b-s))<0;
}
bool cmp3(vec a,vec b)
{
    return ((a-t)^(b-t))>0;
}
bool cmp4(vec a,vec b)
{
    return ((a-t)^(b-t))<0;
}
ll ans,res;
bool judge(vec a,vec b,vec c,vec d)
{
    ll t1=(a-b)^(b-c),t2=(a-b)^(b-d);
    return t1*t2<=0;
}
bool jiao(vec a,vec b,vec c,vec d)//线段相交
{
    return judge(a,b,c,d)&&judge(c,d,a,b);
}
void solve()
{
    t1=t2=0;
    for(int i=1;i<=n;i++)
    {
        if(c[i]==s||c[i]==t) continue;
        if(((t-s)^(c[i]-s))>0) a[++t1]=c[i],a[t1].id=t1;//线段t-s上的点
        else b[++t2]=c[i],b[t2].id=t2;//线段t-s下的点
    }
    ans+=t1*(t1-1)*(t1-2)/6;//线段上的三角形
    ans+=t2*(t2-1)*(t2-2)/6;//线段下的三角形
    sort(a+1,a+1+t1,cmp1);
    sort(b+1,b+1+t2,cmp1);
    //线段左边的三角形
    for(int i=1,j=1;i<=t1;i++)
    {
        while(j<=t2&&(jiao(s,t,a[i],b[j])||!jiao(s,t,a[i],b[j])&&((a[i]-b[j])^(s-b[j]))<0)) j++;
        ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2;
        le[a[i].id]=t2-j+1;
    }
    sort(a+1,a+1+t1,cmp4);
    sort(b+1,b+1+t2,cmp4);
    //线段右边的三角形
    for(int i=1,j=1;i<=t1;i++)
    {
        while(j<=t2&&(jiao(s,t,a[i],b[j])||!jiao(s,t,a[i],b[j])&&((a[i]-b[j])^(s-b[j]))>0)) j++;
        ans+=(t2-j+1)*(i-1)+(t2-j+1)*(t2-j)/2;
        ri[a[i].id]=t2-j+1;
    }
    for(int i=1;i<=t1;i++) ans+=le[i]*ri[i];//包含线段,上一个点下两个点
    sort(a+1,a+1+t1,cmp2);
    sort(b+1,b+1+t2,cmp2);
    for(int i=1,j=1;i<=t2;i++)
    {
        while(j<=t1&&(jiao(s,t,a[j],b[i])||!jiao(s,t,a[j],b[i])&&((a[j]-b[i])^(s-b[i]))<0)) j++;
        le[b[i].id]=t1-j+1;
    }
    sort(a+1,a+1+t1,cmp3);
    sort(b+1,b+1+t2,cmp3);
    for(int i=1,j=1;i<=t2;i++)
    {
        while(j<=t1&&(jiao(s,t,a[j],b[i])||!jiao(s,t,a[j],b[i])&&((a[j]-b[i])^(s-b[i]))>0)) j++;
        ri[b[i].id]=t1-j+1;
    }
    for(int i=1;i<=t2;i++) ans+=le[i]*ri[i];//包含线段,上两个点下一个点
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) c[i].sc();
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)//枚举线段
    {
        s=c[i];t=c[j];
        solve();
    }
    printf("%lld\n",ans);
}
	
全部评论
实测 n^3 log n 常数很大,预处理出极角序能做到 n^3 才能过。感觉你这代码思路没啥问题,至于为什么错了可能是双指针细节写挂了?
点赞 回复 分享
发布于 2020-06-06 22:45

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
04-22 18:57
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务