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

#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

相关推荐

2025-12-02 02:15
门头沟学院
最近菊厂陆续开了,极力劝退那些拿13级的985硕士,就13级那么点儿薪资,一线城市每个月到手1.8/7/6w,租房2k还是破烂,吃饭2k还是预制菜,买个1k衣服都是聚酯纤维破塑料,稍微出去浪一浪,能留1w就是万岁,要是再有个啥都想买的对象,一线工作一年难存10w。隔壁工地混泥土,钳工,焊工一天800+,还包吃包住。读书18年到985硕士出来就为了进厂螺丝工?还不如从8岁童工开始干活,别人读书完了你工龄18+,混不上领导也是个小头头了。当然专科进来正式工,od都行,一般本科进来13级也OK,毕竟22岁年纪摆在那个地方还不需要太花钱。读硕博的基本26岁,工作两年就要结婚的,兜里没几个崽,连彩礼都要信用贷。菊厂离职的不少,毕竟正常没人受得了9116(梗:再来一次911刷6)。为啥这时候劝?因为刚下班,因为国考刚完,省考下周,就是可惜选调只有当年应届能报。现在回想能拍断大腿。应届生真实好身份,错过这一次,选调,考公,考编,当老师,进医院,研究所,高校,央国企,基本都无缘了,就连报名资格都被剥夺了,可谓是被党和国家遗弃的废材,统称“社会上的”,扔到社会去流浪,被用坏了就扔医院,长期超负载使用,零件修不好基本可以扔火里回炉重造了。体制内奉行找体制内的,都是党和国家选的人才,智力不差,样貌不丑,身材端正,收入稳定,安居房政策福利待遇也OK。因公出行都是报销,周末顺带“游山玩水“,这种体制内单身资源但凡想找对象,去社会上随便吆喝一声都排队。观察一下,基本没什么公务员在相亲,因为早就被邻里邻居抢光了。
哈哈哈,你是老六:就这不去的人大把人干呢,现在不缺人干活,你不干大把干呢,还有那个说农民工赚钱的,那个800+我估计肯定也就那一段时间,哪有这么赚钱,还是一句话,要想存下钱必须花销极低,能省的就不花钱,工资要高点
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务