Contents
Area Sums in Convex Polygons PLYARSM Solution
You are given a convex polygon P with N vertices. The vertices (in clockwise order) are v1,v2,…vN. The coordinates of vi are (xi,yi). All vertices have integer coordinates.
A diagonal of P is a line segment l joining two distinct vertices vi and vj of P, such that l is not already an edge of P. Every diagonal of P splits it into two smaller convex polygons, both having positive areas.
The evenness of a diagonal of P is the minimum of the areas of the two parts obtained when the polygon P is cut along this diagonal.
Let S be the sum of the evenness of all diagonals of P.
Find the value of 2S(mod998244353).
It can be shown that for all polygons P with integer coordinates, the value 2S is an integer.
Input Format
- The first line of input contains an integer T, denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N, the number of vertices of the convex polygon P. This is followed by N lines describing the points of the convex polygon, in clockwise order.
- The ith subsequent line contains two space-separated integers, xi,yi the coordinates of vi.
Output Format
For each test case, print a new line with a single integer, the answer as per the problem statement.
Constraints
- 1≤T≤105
- 3≤N≤105
- The sum of N over all test cases does not exceed 106
- The given polygon PP is convex
- Every coordinate is an integer whose absolute value does not exceed 108
Subtasks
Subtask #1 ( 5 points): Sum of N over all test cases does not exceed 500
Subtask #2 (15 points): Sum of N over all test cases does not exceed 2000
Subtask #3 (80 points): Original constraints
Sample Input 1
4
4
-1 0
0 1
1 0
0 -1
4
-100000 0
0 100000
100000 0
0 -100000
3
0 0
0 1
1 0
5
-87260 82619
-59348 68595
86583 -16668
85637 -45559
-49307 -31316Sample Output 1
4
70225880
0
667956140Explanation
Test case 1: The given polygon is a square with side length 2–√2. There are only two diagonals, both are identical and split the polygon equally into two halves each with area (2√)22=1. Thus S=min(1,1)+min(1,1)=2. The value of 2S(mod998244353) is thus 4.
Test case 2: The given polygon is identical to the previous case, except that all coordinates are multiplied by 105105. Therefore the given sum gets multiplied by (105)2. Make sure you output the sum modulo 998244353. Here 2S=4⋅1010 and 4⋅1010(mod998244353)=70225880.
Test case 3: There are no diagonals in this polygon, and so the answer is 0.
SOLUTION
Program: Area Sums in Convex Polygons PLYARSM Solution in C++
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
#define pb push_back
#define pf push_front
#define mp make_pair
#define pi vector <pair<int, ll >>
#define ll long long int
#define mod 998244353
#define fi first
#define Endl endl
#define se second
#define all(a) a.begin(),a.end()
#define in(n) ll n;cin>>n
#define in2(n,k) ll n,k; cin>>n>>k
bool ispow(ll a){
ll f=1;
if(a==1){
return false;
}
while(a!=1){
if(a%2){
f=0;
break;
}
a/=2;
}
if(f)
return true;
else
return false;
}
struct DSU{
vector<int> parent;
vector<set<int>> box;
void initialize(int n){
parent.resize(n);
iota(all(parent),0);
box.resize(n);
for(int i=0;i<n;i++){
box[i].clear();
box[i].insert(i);
}
}
int pr(int a){
if(parent[parent[a]]!=parent[a])
parent[a]=pr(parent[a]);
return parent[a];
}
void merge(int a,int b){
a=pr(a);
b=pr(b);
if(a==b)
return;
if(box[b].size()>box[a].size())
swap(a,b);
parent[b]=a;
for(auto u : box[b])
box[a].insert(u);
box[b].clear();
return;
}
};
struct coord{
ll x;
ll y;
};
inline ll triangleArea(coord a,coord b,coord c){
return (abs((a.x*(b.y-c.y))+(b.x*(c.y-a.y))+(c.x*(a.y-b.y))));
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
ll t=1;
cin>>t;
while(t--){
in(n);
vector<coord> v(n);
for(int i=0;i<n;i++)
cin>>v[i].x>>v[i].y;
if(n==3){
cout<<0<<endl;
}
else{
ll tot=0;
ll kri=0;
vector<ll> prod(n,0),pre(n,0),prepre(n,0),px(n,0),py(n,0),pxy(n,0);
px[0]=(v[0].x+mod)%mod;
py[0]=(v[0].y+mod)%mod;
pxy[0]=(v[0].x*v[0].y+mod)%mod;
if(pxy[0]<0)
pxy[0]+=mod;
for(int i=1;i<n;i++)
px[i]=(px[i-1]+v[i].x+mod)%mod;
for(int i=1;i<n;i++)
py[i]=(py[i-1]+v[i].y+mod)%mod;
for(int i=1;i<n;i++)
pxy[i]=(pxy[i-1]+(v[i].y*v[i].x)+(mod))%mod;
for(int i=2;i<n;i++){
tot+=triangleArea(v[0],v[i-1],v[i]);
}
for(int i=0;i+1<n;i++){
prod[i]=(v[i].x+v[i+1].x)*(v[i].y-v[i+1].y);
}
pre[0]=prod[0];
for(int i=1;i+1<n;i++){
pre[i]=pre[i-1]+prod[i];
}
prepre[0]=(pre[0]+(mod))%mod;
if(prepre[0]<0)
prepre[0]+=mod;
for(int i=1;i+1<n;i++){
prepre[i]=(prepre[i-1]+pre[i]+mod)%mod;
}
for(int v1=0;v1<1;v1++){
ll temp=0;
for(int v2=v1+2;v2<n;v2++){
temp+=triangleArea(v[v1],v[v2-1],v[v2]);
kri+=min(temp,tot-temp);
kri=kri%mod;
}
}
for(int v1=1;v1+2<n;v1++){
ll hi=n-1;
ll lo=v1+2;
ll idx=lo-1;
while(hi>=lo){
ll mid=(hi+lo)/2;
ll curr=pre[mid-1]-pre[v1-1];
curr+=(v[v1].x+v[mid].x)*(v[mid].y-v[v1].y);
if(curr<=tot-curr){
lo=mid+1;
idx=max(idx,mid);
}
else{
hi=mid-1;
}
}
ll add=0;
ll p=tot%mod;
p=(p*(n-1-idx))%mod;
if(idx>=v1+2){
ll temp=(prepre[idx-1]-prepre[v1]+mod)%mod;
ll z=(pre[v1-1]+mod)%mod;
z*=(idx-v1-1);
z%=mod;
temp=(temp-z+mod)%mod;
z=((v[v1].x)*((py[idx]-py[v1+1]+mod)%mod))%mod;
ll g=(idx-v1-1);
g*=(v[v1].x*v[v1].y+mod)%mod;
g%=mod;
ll h=(pxy[idx]-pxy[v1+1]+mod)%mod;
ll r=(((v[v1].y)*((px[idx]-px[v1+1]+mod)%mod))%mod);
temp=(temp-r-g+h+z+mod)%mod;
add=temp;
kri+=temp;
kri%=mod;
}
idx=n-1;
ll temp=(prepre[idx-1]-prepre[v1]+mod)%mod;
ll z=(pre[v1-1]+mod)%mod;
z*=(idx-v1-1);
z%=mod;
temp=(temp-z+mod)%mod;
z=((v[v1].x)*((py[idx]-py[v1+1]+mod)%mod))%mod;
ll g=(idx-v1-1);
g*=(v[v1].x*v[v1].y+mod)%mod;
g%=mod;
ll h=(pxy[idx]-pxy[v1+1]+mod)%mod;
ll r=(((v[v1].y)*((px[idx]-px[v1+1]+mod)%mod))%mod);
temp=(temp-r-g+h+z+mod)%mod;
temp=(temp-add+mod)%mod;
kri+=p;
kri%=mod;
kri=(kri-temp+mod)%mod;
}
cout<<kri;
cout<<endl;
}
}
return 0;
}