QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466228#8468. Collinear ArrangementsLRWA 0ms8756kbC++204.4kb2024-07-07 17:02:472024-07-07 17:02:47

Judging History

你现在查看的是最新测评结果

  • [2024-07-07 17:02:47]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:8756kb
  • [2024-07-07 17:02:47]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second

using namespace std;
const int maxn = 2e5 + 5;
int n, q;
ii a[maxn];

inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

inline int rand(int l, int r)
{
    uniform_int_distribution<int> rg(l, r);
    return rg(rng);
}


/**
    A, B, C collinear
    when
    (Ax - Bx) / (Ay - By) == (Bx - Cx) / (By - Cy)

**/

bool cw(ii &a, ii &b, ii &c)
{
    int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
    return ans > 0;
}

bool ccw(ii &a, ii &b, ii &c)
{
    int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
    return ans < 0;
}

bool collinear(ii &a, ii &b, ii &c)
{
    int ans = (b.ff - a.ff) * (b.ss + a.ss) + (c.ff - b.ff) * (c.ss + b.ss) + (a.ff - c.ff) * (a.ss + c.ss);
    return ans == 0;
}

struct Vec
{
	int x,y;
	Vec(int a=0,int b=0) {x=a,y=b;}
};
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (const Vec &x,const int y) {return Vec(x.x*y,x.y*y);}
Vec operator / (const Vec &x,const int y) {return Vec(x.x/y,x.y/y);}
int cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
int cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int norm(Vec x) {return x.x*x.x+x.y*x.y;}
Vec rot90(Vec x) {return Vec(x.y,-x.x);}
Vec A[maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i].ff >> a[i].ss,
        a[i + n] = a[i];
    for (int i = 1; i <= n * 2 + 1; i++)
        A[i] = Vec(a[(i - 1) % n + 1].ff, a[(i - 1) % n + 1].ss);
    while (q--)
    {
        int t; ii x, y;
        cin >> t;
        if (t == 1)
        {
            cin >> x.ff >> x.ss;
            int ans = 0;
            for (int i = 1; i <= n; i++)
            {
                int l = i + 1, r = i + n - 1, yes = 0;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if (cw(a[i], x, a[mid])) l = mid + 1;
                    else if (ccw(a[i], x, a[mid])) r = mid - 1;
                    else
                    {
                        yes = mid;
                        break;
                    }
                }
                l = i + 1, r = i + n - 1;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if (cw(a[i], x, a[mid])) r = mid - 1;
                    else if (ccw(a[i], x, a[mid])) l = mid + 1;
                    else
                    {
                        yes = mid;
                        break;
                    }
                }
                ans += yes > 0;
            }
            cout << ans / 2 << "\n";
        }
        else
        {
            Vec P,Q;
			cin >> P.x >> P.y >> Q.x >> Q.y;
			Vec v=rot90(Q-P);
			int orig=1;
			while(cdot(A[orig+1]-A[orig],v)==0) orig++;
			int c1=orig;
			if(cdot(A[c1+1]-A[c1],v)<0) v=v*(-1);
			// printf("%d %d\n",v.x,v.y);
			for(int i=17;i>=0;i--)
			{
				if(c1+(1<<i)<=orig+n-1)
				{
					int tw=c1+(1<<i);
					if(cdot(v,A[tw+1]-A[tw])>0&&cdot(v,A[tw]-A[c1])>=0) c1+=(1<<i);
				}
			}
			c1=c1%n+1;
			int c2=c1;
			v=v*(-1);
			// printf("%d %d\n",v.x,v.y);
			// cout<<cdot(v,A[tw]-A[i])<<endl;
			for(int i=17;i>=0;i--)
			{
				if(c2+(1<<i)<=c1+n-1)
				{
					int tw=c2+(1<<i);
					if(cdot(v,A[tw+1]-A[tw])>0&&cdot(v,A[tw]-A[c2])>=0) c2+=(1<<i);
				}
			}
			c2++;
			// printf("%d %d\n",c1,c2);
			auto find=[&](int l,int r)->int
			{
				int o=cross(Q-P,A[l]-P);
				if(o==0) return 1;
				while(l<=r)
				{
					int mid=(l+r)/2;
					int tw=cross(Q-P,A[mid]-P);
					if(tw==0) return 1;
					if((tw>0)==(o>0)) l=mid+1;
					else r=mid-1;
				}
				return 0;
			};
			int ans=0;
			ans+=find(c1+1,c2);
			ans+=find(c2+1,c1+n);
			printf("%lld\n",ans);
        }
    }
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 8756kb

input:

5 3
0 0
2 0
2 1
1 2
0 2
1 1 1
2 1 1 2 2
1 2 2

output:

1
2
1

result:

wrong answer 2nd numbers differ - expected: '1', found: '2'