标签存档：计算几何

【题目翻译】http://www.wzoi.org/usaco/15%5C305.asp

【算法分析】

矩形切割，直接模拟就可以。

【其它】囧，以前居然卡在这题水题上。1A

USER: wei jie chen [jie22221]TASK: windowLANG: C++Compiling…Compile: OKExecuting… Test 1: TEST OK [0.000 secs, 2804 KB] Test 2: TEST OK [0.000 secs, 2804 KB] Test 3: TEST OK [0.000 secs, 2804 KB] Test 4: TEST OK [0.011 secs, 2804 KB] Test 5: TEST OK [0.011 secs, 2804 KB] Test 6: TEST OK [0.011 secs, 2804 KB] Test 7: TEST OK [0.022 secs, 2804 KB] Test 8: TEST OK [0.022 secs, 2804 KB] Test 9: TEST OK [0.000 secs, 2804 KB] Test 10: TEST OK [0.000 secs, 2804 KB] Test 11: TEST OK [0.022 secs, 2804 KB]All tests OK.

YOUR PROGRAM (‘window’) WORKED FIRST TIME! That’s fantastic– and a rare thing. Please accept these special automatedcongratulations.

【CODE】

/*
ID:jie22221
TASK:window
LANG:C++
*/
#include #include #include #include #include using namespace std;
const int N=100;
struct zfx{int x1,y1,x2,y2;char mark;}d[N];
int n;
double ans;inline int area(int x1,int y1,int x2,int y2){
    return (x2-x1)*(y2-y1);
}    void cut(int i,int x1,int y1,int x2,int y2){
    if (x1>=x2 || y1>=y2) return;
    if (i>n){
        ans+=area(x1,y1,x2,y2);
        return;
    }   
    if (x1    if (x2>d[i].x2) cut(i+1,max(x1,d[i].x2),y1,x2,y2);
    if (y1    if (y2>d[i].y2) cut(i+1,max(x1,d[i].x1),max(d[i].y2,y1),min(x2,d[i].x2),y2);
}   int main(){
    freopen("window.in","r",stdin);
    freopen("window.out","w",stdout);
    char op;
    int pos;
    zfx tmp;
    for (;;){
        op=’ ‘;
        while (scanf("%c",&op)!=EOF && (op==’ ‘ || op==’n’));
        if (op==’ ‘ || op==’n’) break;
        switch (op){
            case ‘w’:
                n++;
                scanf("(%c,%d,%d,%d,%d)",&d[n].mark,&d[n].x1,&d[n].y1,&d[n].x2,&d[n].y2);
                if (d[n].x1>d[n].x2) swap(d[n].x1,d[n].x2);
                if (d[n].y1>d[n].y2) swap(d[n].y1,d[n].y2);
                break;
            case ‘t’:
                scanf("(%c)",&op);
                zfx tmp;
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                tmp=d[pos];
                for (int i=pos;i                d[n]=tmp;
                break;
            case ‘b’:
                scanf("(%c)",&op);
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                tmp=d[pos];
                for (int i=pos;i>1;i–) d[i]=d[i-1];
                d[1]=tmp;
                break;
            case ‘d’:
                scanf("(%c)",&op);
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                for (int i=pos;i                n–;
                break;
            case ‘s’:
                scanf("(%c)",&op);
                for (pos=1;pos<=n;pos++)
                  if (d[pos].mark==op) break;
                ans=0;
                cut(pos+1,d[pos].x1,d[pos].y1,d[pos].x2,d[pos].y2);
                double S=area(d[pos].x1,d[pos].y1,d[pos].x2,d[pos].y2);
                printf("%.3lfn",ans/S*100);
                break;
        }   
    }   
}   

【题目大意】

给出N个凸多边形（坐标按逆时针给出），让你求面积交。

【其它】1A

194906 edward_mj 1156 Accepted 184K 15MS G++ 1.73K 2010-02-15 17:53:10

【CODE】

#include #include struct point{double x,y;};
struct line{double a,b,c;};
point p[1000000],pt[1000000],pre,now,st,O;
int n,tot;

void init(){
     O.x=0; O.y=0;
     scanf("%d%d",&tot,&n);
     for (int i=1;i<=n;i++)
         scanf("%lf%lf",&p[i].x,&p[i].y);
}

double X(point p0,point p1,point p2){
       return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

line getline(point p1,point p2){
     line New;
     New.a=p1.y-p2.y;
     New.b=p2.x-p1.x;
     New.c=X(p1,p2,O);
     return New;
}

point jiaodian(point p1,point p2,point p3,point p4){
      point New;
      line l1=getline(p1,p2),l2=getline(p3,p4);
      double tmp=l1.a*l2.b-l2.a*l1.b;
      New.x=(l1.b*l2.c-l2.b*l1.c)/tmp;
      New.y=-(l1.a*l2.c-l2.a*l1.c)/tmp;
      return New;
}

void cut(){
     int N=0;
     p[n+1]=p[1];
     for (int i=2;i<=n+1;i++)
       if (X(pre,now,p[i-1])<0){
            if (X(pre,now,p[i])>0)
              pt[++N]=jiaodian(pre,now,p[i-1],p[i]);
       }
       else{
            pt[++N]=p[i-1];
            if (X(pre,now,p[i])<0)
              pt[++N]=jiaodian(pre,now,p[i-1],p[i]);
       }
     for (int i=1;i<=N;i++) p[i]=pt[i];
     n=N;
}

void work(){
     int m;
     for (int i=1;i       scanf("%d",&m);
       scanf("%lf%lf",&st.x,&st.y);
       pre=st;
       for (int i=1;i           scanf("%lf%lf",&now.x,&now.y);
           cut();
           pre=now;
       }
       now=st;
       cut();
     }
}

void print(){
     p[n+1]=p[1];
     double ans=0;
     for (int i=1;i<=n;i++)
       ans+=(p[i].x*p[i+1].y-p[i+1].x*p[i].y)/2;
     ans=fabs(ans);
     printf("%.3lfn",ans);
}

int main(){
    init();
    work();
    print();
}

【题目】http://202.115.160.24:8080/JudgeOnline/showproblem?problem_id=1136

【算法分析】

偶模仿http://hi.baidu.com/zyylhappy/blog/item/4ec2410b67e07f2f6a60fb0b.html这个写的。。。

现在基本是理解了。

【其他】1A，第一个半平面交。

143257 edward_mj 1136 Accepted 276K 0MS G++ 1.78K 2010-02-15 17:26:51

【CODE】

#include