QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#253363#6703. Tokens on the SegmentsZsc10014WA 0ms3880kbC++172.1kb2023-11-16 22:06:282023-11-16 22:06:29

Judging History

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

  • [2023-11-16 22:06:29]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3880kb
  • [2023-11-16 22:06:28]
  • 提交

answer

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<set>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
#define int long long
#define double long double

inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
       if(c=='-') f=-1;
        c=getchar();
    }
    while('0'<=c&&c<='9')
    {
       x=(x<<3) +(x<<1) +(c^48);
       c=getchar();
    }
    return x*f;
}

const int maxn = 100005;
int x[maxn],y[maxn];
int n,k;

int cross(int p,int q)
{
    return ( x[p]*y[q] - x[q]*y[p] );
}

int cal(int p1,int p2,int p)
{
    int p3 = (p2+p)%n;
    int x1 = x[p2]-x[p1];
    int x2 = x[p3]-x[p1];
    int y1 = y[p2]-y[p1];
    int y2 = y[p3]-y[p1];
    int temp = (x1*y2-x2*y1);
    return fabs(temp);
}

signed main()
{
    int T=read();
    while(T--)
    {   
        n=read(); k=read();
        for(int i=0;i<n;++i) x[i]=read(),y[i]=read();
        int ans = 0;
        int sum = 0;
        int area = 0;
        int b = 0,c = (b+k)%n;
        for(int i=b;i<c;++i)
            sum += cross( i%n , (i+1) %n );//sum of cross
        for(int b=0;b<n;++b)
        {   
            c = (b+k)%n;
            if(b!=0) 
            {
                sum -= cross(b-1,b);
                sum += cross( (c-1+n)%n ,c%n);
            }
            area = fabs( sum + cross(c,b) ) ;//the area of the (b to c)
            if(k==1) area = 0;
            int rsum = 0;
            int l = 1 , r = n - k - 1;
            int lmid,rmid;
            int lans,rans;
            while(r-l>=3)
            {   
                lmid = l + (r-l)/3;
                rmid = r - (r-1)/3;
                lans = cal(b,c,lmid);
                rans = cal(b,c,rmid);//the area of the triangle     
                if(rans > lans) r = rmid-1;
                else l = lmid+1;
                rsum = max(rsum,max(lans,rans));
            }
            for(int i=l;i<=r;++i) rsum = max(rsum, cal(b,c,i) );
            ans = max(ans,area + rsum);
        }
        printf("%.12lf\n",0.5*ans);
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
3
1 2
1 1
2 3
3
1 2
1 1
2 2

output:

1.500000000000
0.000000000000

result:

wrong output format Expected integer, but "1.500000000000" found