今度は#64、Div.1のハイレベルな人も参加するコンテストに参加してきました。
Aから順に問題を読んでいきますが、なかなか理解がはかどりません。一通り読み終えた段階で30分、何とかなりそうか？と思ってCをやりますが、全くにっちもさっちも行きません。仕方がないので、Dにくら替えして、この段階で残り1時間5分。
Dは、非常に数学的な問題で、ものすごく単純には「入力される点が入力される凸多角形の内部に入っているかどうか判定」する問題でした。ただ、入っているかどうかの判定方法は思い当たらなかったので、自分で20分強試行錯誤して導き出しました。
導いたのは「判定点から多角形の各頂点へのベクトルを求め、これが連続180度未満に分布していれば判定点は外側にある」というもの。その方針で書いていって、30分ほどで、何とか書き上げました。
そして提出すると…なんと、pretest5で引っかかったという報告が！慌てて直しますが、時間切れで、結局一問も解けませんでした。話にならないもんだなぁ…。
あとで結果を見ると、この問題の正解者は8/897。挑もうとしたのが無謀だったのかもしれません。
問題はこちら。
当該問題のソースは、続きに載せておきます。
以下がDの(誤りが出る)ソースです。時間を気にして整数演算にしたのですが、もっと愚直に解いたほうが正解だったのかもしれません。
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
typedef struct{
int x;
int y;
}point;
typedef struct{
point p;
int where;
}vec;
vec getvec(point a,point b);
int main(void){
int i,j,k,n,types;
int recnum=3,flgs[5];
double maxval,minval;
point *firm;
point input;
vec *vectors,rha,lha;
scanf("%d",&n);
firm=(point *)calloc(3,sizeof(point));
for(i=0;i<3;i++) scanf("%d %d %d",&types,&(firm+i)->x,&(firm+i)->y);
for(i=3;i<n;i++){
scanf("%d %d %d",&types,&input.x,&input.y);
if(types==1){
firm=realloc(firm,(recnum++)*sizeof(point));
*(firm+recnum)=input;
}else if(types==2){
for(j=0;j<5;j++) flgs[j]=0;
for(j=0;j<recnum;j++){
vectors=(vec *)calloc(recnum,sizeof(vec));
*(vectors+j)=getvec(*(firm+j),input);
flgs[(vectors+j)->where]=1;
}
if(abs(flgs[1]+flgs[3]-flgs[2]-flgs[4])==2){
puts("YES");
free(vectors);
continue;
}
flgs[0]=flgs[1]+flgs[2]+flgs[3]+flgs[4];
if(flgs[0]<=2){
puts("NO");
free(vectors);
continue;
}else if(flgs[0]==4){
puts("YES");
free(vectors);
continue;
}
maxval=minval=0;
if(flgs[1]==0){
flgs[0]=0;
for(k=0;k<recnum;k++){
switch(vectors[k].where){
case 2:
if(vectors[k].p.x==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.y/vectors[k].p.x)>maxval){
maxval=fabs((double)vectors[k].p.x/vectors[k].p.y);
rha=vectors[k];
}
break;
case 4:
if(vectors[k].p.y==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.x/vectors[k].p.y)>minval){
minval=fabs((double)vectors[k].p.x/vectors[k].p.y);
lha=vectors[k];
}
break;
}
if(flgs[0]==-2) break;
}
free(vectors);
if(lha.p.x==-rha.p.x && lha.p.y==-rha.p.y){
puts("YES");
continue;
}
if(rha.p.x*lha.p.y>rha.p.y*lha.p.x){
puts("NO");
continue;
}
puts("YES");
continue;
}else if(flgs[2]==0){
flgs[0]=0;
for(k=0;k<recnum;k++){
switch(vectors[k].where){
case 1:
if(vectors[k].p.x==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.y/vectors[k].p.x)>maxval){
maxval=fabs((double)vectors[k].p.x/vectors[k].p.y);
rha=vectors[k];
}
break;
case 3:
if(vectors[k].p.y==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.x/vectors[k].p.y)>minval){
minval=fabs((double)vectors[k].p.x/vectors[k].p.y);
lha=vectors[k];
}
break;
}
if(flgs[0]==-2) break;
}
free(vectors);
if(lha.p.x==-rha.p.x && lha.p.y==-rha.p.y){
puts("YES");
continue;
}
if(rha.p.x*lha.p.y>rha.p.y*lha.p.x){
puts("NO");
continue;
}
puts("YES");
continue;
}else if(flgs[3]==0){
flgs[0]=0;
for(k=0;k<recnum;k++){
switch(vectors[k].where){
case 4:
if(vectors[k].p.x==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.y/vectors[k].p.x)>maxval){
maxval=fabs((double)vectors[k].p.x/vectors[k].p.y);
rha=vectors[k];
}
break;
case 2:
if(vectors[k].p.y==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.x/vectors[k].p.y)>minval){
minval=fabs((double)vectors[k].p.x/vectors[k].p.y);
lha=vectors[k];
}
break;
}
if(flgs[0]==-2) break;
}
free(vectors);
if(lha.p.x==-rha.p.x && lha.p.y==-rha.p.y){
puts("YES");
continue;
}
if(rha.p.x*lha.p.y>rha.p.y*lha.p.x){
puts("NO");
continue;
}
puts("YES");
continue;
}else if(flgs[4]==0){
flgs[0]=0;
for(k=0;k<recnum;k++){
switch(vectors[k].where){
case 3:
if(vectors[k].p.x==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.y/vectors[k].p.x)>maxval){
maxval=fabs((double)vectors[k].p.x/vectors[k].p.y);
rha=vectors[k];
}
break;
case 1:
if(vectors[k].p.y==0){
flgs[0]--;
rha=vectors[k];
break;
}
if(fabs((double)vectors[k].p.x/vectors[k].p.y)>minval){
minval=fabs((double)vectors[k].p.x/vectors[k].p.y);
lha=vectors[k];
}
break;
}
if(flgs[0]==-2) break;
}
free(vectors);
if(lha.p.x==-rha.p.x && lha.p.y==-rha.p.y){
puts("YES");
continue;
}
if(rha.p.x*lha.p.y>rha.p.y*lha.p.x){//
puts("NO");
continue;
}
puts("YES");
continue;
}
}
}
free(firm);
return 0;
}
vec getvec(point a,point b){
vec c;
c.p.x=a.x-b.x;
c.p.y=a.y-b.y;
if(c.p.x>0 && c.p.y>=0) c.where=1;
else if(c.p.x<=0 && c.p.y>0) c.where=2;
else if(c.p.x<0 && c.p.y<=0) c.where=3;
else c.where=4;
return c;
}
0 件のコメント:
コメントを投稿