「BZOJ2391」Cirno的忧郁

2014年6月13日5,4630

Description

Cirno闲着无事的时候喜欢冰冻青蛙。

Cirno每次从雾之湖中固定的n个结点中选出一些点构成一个简单多边形，Cirno运用自己的能力能将此多边形内所有青蛙冰冻。

雾之湖生活着m只青蛙,青蛙有大有小，所以每只青蛙的价值为一个不大于10000的正整数。

Cirno很想知道每次冻住的青蛙的价值总和。因为智商有限，Cirno将这个问题交给完美算术教室里的你。

因为爱护动物，所以每次冻结的青蛙会被放生。也就是说一只青蛙可以被多次统计。

Input

第一行2个正整数 n,m。

以下n行，每行2个整数xi,yi,表示第i个结点的坐标。

再以下m行，每行3个整数xj,yj,vj，表示第j个青蛙的坐标和价值。

第n+m+1行一个整数q，表示有q组询问。

每组询问有2行，第一行一个整数s（3<=s<=n），表示简单多边形的结点数。第二行s个正整数，顺时针或逆时针给出多边形的结点的编号(1–n)

Output

q行。

对于每个询问，每行输出一个整数表示冻结的青蛙的价值之和

Sample Input

4 3
2 2
3 5
7 4
5 1
3 4 2
4 3 7
6 3 90
2
3
1 2 3
4
1 4 3 2

Sample Output

9
99

HINT

「数据范围」

对于30%的数据，n,m<=100; q<=100

对于60%的数据，n,m<=100; q<=10000

对于100%的数据，n,m<=1000; q<=10000

-10000<=x,y<=10000; 0<v<=10000

题解

参照JoyOI1360…

才刚刚知道这货叫三角剖分。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
using namespace std;
//=========================================
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//========================================= 快速读入 
int n,m,q,x,y,cnt;
int root,sz,tmp,ans;
int ls[2005],rs[2005],c[2005],sum[2005],num[2005],rnd[2005];
int b[2005],mark[2005];
int f[2005][2005];
struct point{int x,y,num,c;}p[2005];
//=========================================
inline point sub(point a,point b)
{point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}
inline int cmul(point a,point b)
{return a.x*b.y-a.y*b.x;}
inline int turn(point a,point b,point c)
{return cmul(sub(c,a),sub(b,a));}
inline int sqr(int x){return x*x;}
inline int dis(point a,point b)
{return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline bool cmp(point a,point b)
{return turn(p[0],a,b)==0?dis(a,p[0])<dis(b,p[0]):turn(a,p[0],b)>0;}
//========================================= 计算几何 
void update(int k)
{sum[k]=sum[ls[k]]+sum[rs[k]]+c[k];}
void rturn(int &k)
{int t=ls[k];ls[k]=rs[t];rs[t]=k;sum[t]=sum[k];update(k);k=t;}
void lturn(int &k)
{int t=rs[k];rs[k]=ls[t];ls[t]=k;sum[t]=sum[k];update(k);k=t;}
void insert(int &k,int id)
{
     if(!k)
     {
         k=++sz;
         ls[k]=rs[k]=0;
         num[k]=id;rnd[k]=rand();
         sum[k]=c[k]=p[id].c;
         return;
     }
     sum[k]+=p[id].c;
     if(turn(p[x],p[num[k]],p[id])>0)
     {
         insert(ls[k],id);
         if(rnd[ls[k]]<rnd[k])rturn(k);
     }
     else 
     {
         insert(rs[k],id);
         tmp+=sum[ls[k]]+c[k];
         if(rnd[rs[k]]<rnd[k])lturn(k);
     }
}
//========================================= 平衡树
void pre()
{
     sort(p+1,p+cnt+1,cmp);
     for(int i=1;i<=cnt;i++)
         mark[p[i].num]=i;
     for(x=1;x<cnt;x++)
     {
         root=sz=0;
         for(y=x+1;y<=cnt;y++)
         {
             tmp=0;
             insert(root,y);
             f[x][y]=tmp;
             f[y][x]=tmp;
         }
     }
}
void getans()
{
    int e=read();
    for(int i=1;i<=e;i++)
        b[i]=read(),b[i]=mark[b[i]];
    b[e+1]=b[1];
    ans=0;
    for(int i=1;i<=e;i++)
        if(turn(p[0],p[b[i]],p[b[i+1]])>0)
            ans+=f[b[i]][b[i+1]];
    else ans-=f[b[i]][b[i+1]];
    if(ans<0)ans=-ans;
    printf("%d\n",ans);
}
int main()
{
    n=read();m=read();
    p[0].x=-12345;p[0].y=-15432;
    for(int i=1;i<=n;i++)
        p[++cnt].x=read(),p[cnt].y=read(),p[cnt].num=cnt;
    for(int i=1;i<=m;i++)
        p[++cnt].x=read(),p[cnt].y=read(),p[cnt].num=cnt,p[cnt].c=read();
    pre();
    q=read();
    for(int i=1;i<=q;i++)
        getans();
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

using namespace std;

//=========================================

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

//========================================= 快速读入

int n,m,q,x,y,cnt;

int root,sz,tmp,ans;

int ls[2005],rs[2005],c[2005],sum[2005],num[2005],rnd[2005];

int b[2005],mark[2005];

int f[2005][2005];

struct point{int x,y,num,c;}p[2005];

//=========================================

inline point sub(point a,point b)

{point t;t.x=a.x-b.x;t.y=a.y-b.y;return t;}

inline int cmul(point a,point b)

{return a.x*b.y-a.y*b.x;}

inline int turn(point a,point b,point c)

{return cmul(sub(c,a),sub(b,a));}

inline int sqr(int x){return x*x;}

inline int dis(point a,point b)

{return sqr(a.x-b.x)+sqr(a.y-b.y);}

inline bool cmp(point a,point b)

{return turn(p[0],a,b)==0?dis(a,p[0])<dis(b,p[0]):turn(a,p[0],b)>0;}

//========================================= 计算几何

void update(int k)

{sum[k]=sum[ls[k]]+sum[rs[k]]+c[k];}

void rturn(int &k)

{int t=ls[k];ls[k]=rs[t];rs[t]=k;sum[t]=sum[k];update(k);k=t;}

void lturn(int &k)

{int t=rs[k];rs[k]=ls[t];ls[t]=k;sum[t]=sum[k];update(k);k=t;}

void insert(int &k,int id)

{

if(!k)

{

k=++sz;

ls[k]=rs[k]=0;

num[k]=id;rnd[k]=rand();

sum[k]=c[k]=p[id].c;

return;

}

sum[k]+=p[id].c;

if(turn(p[x],p[num[k]],p[id])>0)

{

insert(ls[k],id);

if(rnd[ls[k]]<rnd[k])rturn(k);

}

else

{

insert(rs[k],id);

tmp+=sum[ls[k]]+c[k];

if(rnd[rs[k]]<rnd[k])lturn(k);

}

//========================================= 平衡树

void pre()

{

sort(p+1,p+cnt+1,cmp);

for(int i=1;i<=cnt;i++)

mark[p[i].num]=i;

for(x=1;x<cnt;x++)

{

root=sz=0;

for(y=x+1;y<=cnt;y++)

{

tmp=0;

insert(root,y);

f[x][y]=tmp;

f[y][x]=tmp;

}

void getans()

{

int e=read();

for(int i=1;i<=e;i++)

b[i]=read(),b[i]=mark[b[i]];

b[e+1]=b[1];

ans=0;

for(int i=1;i<=e;i++)

if(turn(p[0],p[b[i]],p[b[i+1]])>0)

ans+=f[b[i]][b[i+1]];

else ans-=f[b[i]][b[i+1]];

if(ans<0)ans=-ans;

printf("%d\n",ans);

}

int main()

{

n=read();m=read();

p[0].x=-12345;p[0].y=-15432;

for(int i=1;i<=n;i++)

p[++cnt].x=read(),p[cnt].y=read(),p[cnt].num=cnt;

for(int i=1;i<=m;i++)

p[++cnt].x=read(),p[cnt].y=read(),p[cnt].num=cnt,p[cnt].c=read();

pre();

q=read();

for(int i=1;i<=q;i++)

getans();

return 0;

}

« 「BZOJ1112」[POI2008] 砖块Klo 「BZOJ1146」[CTSC2008] 网络管理Network »

hzwer.com _ Home | http://hzwer.com

「BZOJ2391」Cirno的忧郁

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论