学习一发平面图的姿势……ref
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
int n, m, k, cnt, uu, vv, nxt[1200005], bel[1200005], belcnt, rot, fa[1200005];
int ask[200005];
bool vis[1200005], isn[1200005];
ll s[1200005], sp[1200005];
struct Point{
int x, y;
Point operator-(const Point &u){
return (Point){x-u.x, y-u.y};
}
ll operator*(const Point &u){
return (ll)x*u.y-(ll)y*u.x;
}
}p[200005];
struct Edge{
int fro, too, idx;
double ang;
Edge(int f=0, int t=0, int i=0){
fro = f; too = t; idx = i;
ang = atan2(p[t].y-p[f].y, p[t].x-p[f].x);
}
bool operator<(const Edge &x)const{
return ang<x.ang;
}
}edge[1200005];
vector<Edge> w[200005], tr[1200005];
void add_edge(int fro, int too){
edge[cnt] = Edge(fro, too, cnt);
w[fro].push_back(edge[cnt]);
cnt++;
}
ll getGcd(ll a, ll b){
return !b?a:getGcd(b, a%b);
}
void rn(int &x){
char ch=getchar();
x = 0;
int f=1;
while(ch<'0' || ch>'9'){
if(ch=='-') f = -1;
ch = getchar();
}
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
x *= f;
}
int findEdge(int f, const Edge &x){
int l=0, r=w[f].size()-1, mid, re;
while(l<=r){
mid = (l + r) >> 1;
if(w[f][mid]<x) l = mid + 1;
else re = mid, r = mid - 1;
}
return re;
}
void dfs(int x){
vis[x] = true;
sp[x] = s[x] * s[x];
s[x] <<= 1;
for(int i=0; i<tr[x].size(); i++){
int t=tr[x][i].too;
if(vis[t]) continue;
fa[t] = x;
isn[tr[x][i].idx] = isn[tr[x][i].idx^1] = true;
dfs(t);
s[x] += s[t];
sp[x] += sp[t];
}
}
int main(){
rn(n); rn(m); rn(k);
for(int i=1; i<=n; i++){
rn(p[i].x);
rn(p[i].y);
}
for(int i=1; i<=m; i++){
rn(uu); rn(vv);
add_edge(uu, vv);
add_edge(vv, uu);
}
for(int i=1; i<=n; i++)
sort(w[i].begin(), w[i].end());
for(int i=0; i<cnt; i++){
int qwq=findEdge(edge[i].too, edge[i^1])-1;
if(qwq==-1) qwq = w[edge[i].too].size() - 1;
nxt[i] = w[edge[i].too][qwq].idx;
}
for(int i=0; i<cnt; i++)
if(!bel[i]){
bel[i] = bel[nxt[i]] = ++belcnt;
for(int j=nxt[i]; edge[j].too!=edge[i].fro; j=nxt[j]){
s[belcnt] += (p[edge[j].fro]-p[edge[i].fro]) * (p[edge[j].too]-p[edge[i].fro]);
bel[nxt[j]] = belcnt;
}
if(s[belcnt]<=0) rot = belcnt;
}
for(int i=0; i<cnt; i++)
tr[bel[i]].push_back(Edge(bel[i], bel[i^1], i));
dfs(rot);
ll p=0, q=0;
int d;
while(k--){
rn(d); d = (d + p) % n + 1;
for(int i=1; i<=d; i++){
rn(ask[i]);
ask[i] = (ask[i] + p) % n + 1;
}
ask[d+1] = ask[1];
p = q = 0;
for(int i=1; i<=d; i++){
int j=w[ask[i]][findEdge(ask[i], Edge(ask[i],ask[i+1],0))].idx;
if(!isn[j]) continue;
if(fa[bel[j]]==bel[j^1])
p += sp[bel[j]], q += s[bel[j]];
else
p -= sp[bel[j^1]], q -= s[bel[j^1]];
}
ll gcd=getGcd(p, q);
p /= gcd; q /= gcd;
printf("%lld %lld
", p, q);
}
return 0;
}