Codeforces Round #250 DIV1 C問題 (1500pt)
Codeforces Round #250 DIV2 E問題 (2500pt)
Problem description
凸とは限らない $N$ 角形が与えられる.
問題文の図のように,$N-2$ 個の三角形に分割する方法が何通りあるかを ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
各頂点間を結ぶことができるかを調べる.
つまり,各頂点間を結んだ時に,その線分は,両端を除いて,全て多角形の内部にあるかどうかを調べる.
後は,まだ分割していない区間を状態にして,DPすれば良い.
時間計算量は $O(N^3)$ になる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}
#define ll long long
#define MD 1000000007
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
#define EPS 1e-10
#define PI 3.141592653589793238462
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
typedef struct struct_point{double x,y;}pnt;
typedef struct struct_line{pnt a,b;}line;
typedef struct struct_circle{pnt c; double r;}circle;
int doubleSign(double a){if(a>EPS) return 1; if(a<-EPS) return -1; return 0;}
int doubleSignR(double a,double b){ if(doubleSign(b)!=0 && doubleSign(a/b-1)==0) return 0; return doubleSign(a-b);}
int pntSign(pnt a){int i=doubleSign(a.x); if(i) return i; return doubleSign(a.y);}
pnt pntPlus(pnt a,pnt b){a.x+=b.x; a.y+=b.y; return a;}
pnt pntMinus(pnt a,pnt b){a.x-=b.x; a.y-=b.y; return a;}
pnt pntMultiple(pnt a,pnt b){pnt c; c.x=a.x*b.x-a.y*b.y; c.y=a.x*b.y+a.y*b.x; return c;}
pnt pntMultipleDouble(pnt a,double k){a.x*=k; a.y*=k; return a;}
int pntIsEqual(pnt a,pnt b){return pntSign(pntMinus(a,b))==0;}
double pntLength(pnt a){return sqrt(a.x*a.x+a.y*a.y);}
double pntLength2(pnt a){return a.x*a.x+a.y*a.y;}
double pntDistance(pnt a,pnt b){return pntLength(pntMinus(a,b));}
double pntDistance2(pnt a,pnt b){return pntLength2(pntMinus(a,b));}
double pntArgument(pnt a){return atan2(a.y,a.x);}
pnt pntNormalize(pnt a){double n=pntLength(a); a.x/=n; a.y/=n; return a;}
double pntInnerProduct(pnt a,pnt b){return a.x*b.x+a.y*b.y;}
double pntOuterProduct(pnt a,pnt b){return a.x*b.y-a.y*b.x;}
pnt pntGenerator(double x,double y){pnt res; res.x=x; res.y=y; return res;}
line pntToLine(pnt a,pnt b){line res; res.a=a; res.b=b; return res;}
circle pntToCircle(pnt c,double r){circle res; res.c=c; res.r=r; return res;}
/* 三角形の符号付面積の2倍 */
double pntAreaOfTriangle2(pnt p1,pnt p2,pnt p3){
double x1,x2,y1,y2;
x1=p2.x-p1.x; x2=p3.x-p1.x;
y1=p2.y-p1.y; y2=p3.y-p1.y;
return x1*y2-x2*y1;
}
/* 符号付面積の符号を返す */
/* p1,p2の直線の左にp3がある場合,戻り値=1 */
/* p1,p2の直線の右にp3がある場合,戻り値=-1 */
/* p1,p2,p3が一直線上にある場合, 戻り値=0 */
int pntSignAreaOfTriangle(pnt p1,pnt p2,pnt p3){
return doubleSign( pntAreaOfTriangle2(p1,p2,p3) );
}
/* 直線の上に載っていると1, 載ってなければ0 */
int isPntOnLine(pnt a,line s){
pnt ab; double r;
ab=pntMinus(s.b,s.a); r=pntDistance(s.a,a)/pntDistance(s.a,s.b);
if( !pntIsEqual(a,pntPlus(s.a,pntMultipleDouble(ab,r)) ) && !pntIsEqual(a,pntMinus(s.a,pntMultipleDouble(ab,r)) ) ) return 0;
return 1;
}
/* 線分の上に載っていると2, 端点なら1, 載ってなければ0 */
int isPntOnSegment(pnt a,line s){
pnt ab; double r;
ab=pntMinus(s.b,s.a); r=pntDistance(s.a,a)/pntDistance(s.a,s.b);
if( !pntIsEqual(a,pntPlus(s.a,pntMultipleDouble(ab,r)) ) ) return 0;
if( doubleSign(r)==-1 || doubleSign(r-1)==1 ) return 0;
if( doubleSign(r)==0 || doubleSign(r-1)==0 ) return 1;
return 2;
}
/* 角度bacを返す */
double angleOfTriangle(pnt a,pnt b,pnt c){
double inner,n1,n2;
inner=pntInnerProduct(pntMinus(b,a),pntMinus(c,a));
n1=pntDistance(a,b); n2=pntDistance(a,c);
inner=inner/n1/n2;
if(inner>1) inner=1; if(inner<-1) inner=-1;
return acos(inner);
}
/* 線分上=1 中=2 外=0 */
int isInPolygon(pnt p,pnt poly[],int size){
int i; double th=0;
poly[size]=poly[0];
rep(i,size) th += pntSignAreaOfTriangle(p,poly[i],poly[i+1]) * angleOfTriangle(p,poly[i],poly[i+1]);
if( -PI/2<th && th<PI/2 ) return 0; return 2;
}
/* 2直線の交点を求める (交わる点が無限大の場合の判定は未実装) */
/* 戻り値: 交点の数 無限大の場合も0を返す */
/* 後の仕様予定: return 2が無限大の場合 */
int pntIntersectionLineLine(line s,line t,pnt *res){
pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b;
double r = (p4.y-p3.y)*(p2.x-p1.x)-(p2.y-p1.y)*(p4.x-p3.x);
if( doubleSign(r)==0 ) return 0;
res->x = (p3.x*p4.y-p3.y*p4.x)*(p2.x-p1.x)-(p1.x*p2.y-p1.y*p2.x)*(p4.x-p3.x);
res->y = (p3.y*p4.x-p3.x*p4.y)*(p2.y-p1.y)-(p1.y*p2.x-p1.x*p2.y)*(p4.y-p3.y);
res->x /= r; res->y /= -r; return 1;
}
/* s=line, t=segment */
int pntIntersectionLineSegment(line s,line t,pnt *res){
pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b;
double x1,x2,y1,y2;
if(pntIntersectionLineLine(s,t,res)!=1) return 0;
x1=MIN(p3.x,p4.x)-EPS; x2=MAX(p3.x,p4.x)+EPS;
y1=MIN(p3.y,p4.y)-EPS; y2=MAX(p3.y,p4.y)+EPS;
if(res->x < x1 || x2 < res->x || res->y < y1 || y2 < res->y) return 0;
if(pntIsEqual(*res,p3)) return 1;
if(pntIsEqual(*res,p4)) return 1;
return 2;
}
/* 2線分の交点を求める (2線分が平行の場合,問答無用で交わらないと判断してしまう) */
/* 戻り値: 2=交わる, 1=端も線分に含めると交わる, 0=交わらない */
int pntIntersectionSegmentSegment(line s,line t,pnt *res){
pnt p1=s.a, p2=s.b, p3=t.a, p4=t.b;
double x1,x2,y1,y2;
if(pntSignAreaOfTriangle(s.a,s.b,t.a)==0 && pntSignAreaOfTriangle(s.a,s.b,t.b)==0){
if(fabs(s.a.x - s.b.x) > fabs(s.a.y - s.b.y)){
x1 = s.a.x; x2 = s.b.x;
y1 = t.a.x; y2 = t.b.x;
} else {
x1 = s.a.y; x2 = s.b.y;
y1 = t.a.y; y2 = t.b.y;
}
if(max(y1,y2) < min(x1,x2) - EPS) return 0;
if(max(x1,x2) < min(y1,y2) - EPS) return 0;
if(max(y1,y2) < min(x1,x2) + EPS) return 1;
if(max(x1,x2) < min(y1,y2) + EPS) return 1;
return 2;
}
if(pntIntersectionLineLine(s,t,res)!=1) return 0;
x1=MIN(p1.x,p2.x)-EPS; x2=MAX(p1.x,p2.x)+EPS;
y1=MIN(p1.y,p2.y)-EPS; y2=MAX(p1.y,p2.y)+EPS;
if(res->x < x1 || x2 < res->x || res->y < y1 || y2 < res->y) return 0;
x1=MIN(p3.x,p4.x)-EPS; x2=MAX(p3.x,p4.x)+EPS;
y1=MIN(p3.y,p4.y)-EPS; y2=MAX(p3.y,p4.y)+EPS;
if(res->x < x1 || x2 < res->x || res->y < y1 || y2 < res->y) return 0;
if(pntIsEqual(*res,p1)) return 1;
if(pntIsEqual(*res,p2)) return 1;
if(pntIsEqual(*res,p3)) return 1;
if(pntIsEqual(*res,p4)) return 1;
return 2;
}
int N, X[210], Y[210];
ll dp[210][210];
int isCan[210][210];
pnt p[210];
ll solve(int a, int b){
int i, j, k;
ll res = 0, tmp;
if(dp[a][b] >= 0) return dp[a][b];
if((a+1)%N==b) return dp[a][b] = 1;
if((a+2)%N==b) return dp[a][b] = 1;
for(i=(a+1)%N;i!=b;i=(i+1)%N) if(isCan[a][i]&&isCan[b][i]){
tmp = solve(a,i) * solve(i,b);
res = (res + tmp) % MD;
}
return dp[a][b] = res;
}
int main(){
int i, j, k, l;
double mnX, mxX, mnY, mxY;
ll res;
line s, t;
pnt ptmp;
reader(&N);
rep(i,N) reader(X+i,Y+i);
mnX = mxX = X[0];
mnY = mxY = Y[0];
rep(i,N){
mnX = min(mnX, (double)X[i]);
mxX = max(mxX, (double)X[i]);
mnY = min(mnY, (double)Y[i]);
mxY = max(mxY, (double)Y[i]);
}
mxX = max(mxX, mnX+1.0);
mxY = max(mxY, mnY+1.0);
rep(i,N) p[i] = pntGenerator((X[i]-mnX)/(mxX-mnX), (Y[i]-mnY)/(mxY-mnY));
REP(i,N,N+3) p[i] = p[i-N];
rep(i,N) REP(j,i,N){
isCan[j][i] = isCan[i][j] = 0;
if(i==j) continue;
if((i+1)%N==j){ isCan[j][i]=isCan[i][j]=1; continue; }
if(i==(j+1)%N){ isCan[j][i]=isCan[i][j]=1; continue; }
s = pntToLine(p[i], p[j]);
rep(k,N){
t = pntToLine(p[k], p[k+1]);
l = pntIntersectionSegmentSegment(s, t, &ptmp);
if(l==2) break;
if(l==1 && (k!=i && k!=j && (k+1)%N!=i && (k+1)%N!=j)) break;
}
if(k < N) continue;
ptmp = pntMultipleDouble( pntPlus(p[i],p[j]), 0.5 );
l = isInPolygon(ptmp, p, N);
if(l==0 || l==1) continue;
isCan[j][i] = isCan[i][j] = 1;
}
rep(i,N) rep(j,N) dp[i][j] = -1;
res = solve(0, N-1);
writer((int)res, '\n');
myed;
return 0;
}
Current time: 2024年03月29日06時44分08秒
Last modified: 2014年12月05日08時39分55秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF250 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)