QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#253363 | #6703. Tokens on the Segments | Zsc10014 | WA | 0ms | 3880kb | C++17 | 2.1kb | 2023-11-16 22:06:28 | 2023-11-16 22:06:29 |
Judging History
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