韦德国际1946英国 > 计算机网络 > 画图问题,计算几何

原标题:画图问题,计算几何

浏览次数:122 时间:2019-11-16

poj1039--Pipe(总计几何卡塔尔

 

题材大要:一条管敬仲有n个折点,给出管敬仲上壁n个点的坐标(x1,y1)(x2,y2)....,x1< p=""> <>

假诺想让光照的最远,那么除了全程的大概外,光一定会与某一个管壁相交,何况会与管中的七个节点相交,否则就能够调动光的角度,使其照的更远,枚举那八个点的职位,然后每一个点处判定相交的岗位。

 

#include 
#include 
#include 
#include 
using namespace std ;
#define eqs 1e-9
/*
两直线相交,求焦点
ax   by   c = 0 ;
ux   vy   w = 0 ;
a/u != b/v 防止平行
交点:( (b*w-v*c)/(a*v-u*b) , (c*u-a*w)/(a*v-u*b) )
*/
struct point
{
    double x , y ;
} p[30];
int n ;
double a[4][4] = { {0,0,0,0},{0,-1,0,0},{0,0,0,-1},{0,-1,0,-1} } ;
double solve(point u,point v) {
    double a = (u.y-v.y)/(u.x-v.x) , b = u.y-a*u.x ;
    double x , y , ans = 0.0 ;
    int flag = 0 , i ;
    y = a*p[0].x   b ;
    if( y-p[0].y >= eqs || p[0].y-1.0-y >= eqs  ) return ans ;
    for(i = 1 ; i < n ; i  ) {
        y = a*p[i].x   b ;
        if( y-p[i].y > eqs ) {
            flag = 1 ;
            break ;
        }
        else if( p[i].y-1.0-y > eqs ) {
            flag = 2 ;
            break ;
        }
        else
            ans  = (p[i].x-p[i-1].x) ;
    }
    if( !flag ) return ans ;
    u = p[i-1] , v = p[i] ;
    if( flag == 2 ) u.y -= 1.0 , v.y -= 1.0 ;
    double k = (u.y-v.y)/(u.x-v.x) , c = u.y-k*u.x ;
    x = (b-c)/(k-a) ;
    ans  = (x-p[i-1].x) ;
    return ans ;
}
int main()
{
    int  i , j , k ;
    double max1 , temp ;
    point u , v ;
    while( scanf(%d, &n) && n )
    {
        max1 = 0.0 ;
        for(i = 0 ; i < n ; i  )
            scanf(%lf %lf, &p[i].x, &p[i].y) ;
        for(i = 0 ; i < n ; i  )
            for(j = i 1 ; j < n ; j  )
                for(k = 0 ; k < 4 ; k  ) {
                    u.x = p[i].x   a[k][0] ; u.y = p[i].y   a[k][1] ;
                    v.x = p[j].x   a[k][2] ; v.y = p[j].y   a[k][3] ;
                    temp = solve(u,v) ;
                    if( temp > max1 )
                        max1 = temp ;
                }
        if( fabs(p[n-1].x-p[0].x-max1) < eqs  )
            printf(Through all the pipe.
) ;
        else
            printf(%.2lf
, p[0].x max1) ;
    }
    return 0 ;
}

 

画图问题,计算几何。 标题大意:一条管敬仲有n个折点,给出管仲上壁n个点的坐标(x1,y1)(x2,y2)....,x1 假如想让光照的最远,那么除了全程的...

  全体的评测用例知足:2 ≤ m, n ≤ 100,0 ≤ q ≤ 100,0 ≤ x < m(x表示输入数据中有所职位的x坐标卡塔 尔(阿拉伯语:قطر‎,0 ≤ y < n(y代表输入数据中装有地点的y坐标卡塔 尔(英语:State of Qatar)。

测量试验用例是没有错的 可是就提交上去以往只得了十分= =
求大神解答

................
... -------- ...
...|CCCCCCCC|...
...|CC ----- ...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC ----- ...
...|CCCCCCCC|...
... -------- ...
................

CSP真题 画图难点 请教
主题素材陈诉
考题编号: 二〇一五12-3
课题名称: 画图
时光范围: 1.0s
内部存款和储蓄器约束: 256.0MB
主题素材叙述:
主题材料陈说
用 ASCII 字符来画图是后生可畏件有意思的业务,并形成了一门被称呼 ASCII Art的主意。比方,下图是用 ASCII 字符画出来的 CSPRO 字样。
..____.____..____..____...___..
./.___/.___||.._.|.._../._..
|.|...___.|.|_).|.|_).|.|.|.|
|.|___.___).|..__/|.._.<|.|_|.|
.____|____/|_|...|_|.____/.
核心供给编制程序达成四个用 ASCII 字符来画图的主次,辅助以下三种操作:
Ÿ 画线:给出四个端点的坐标,画一条连接那四个端点的线条。简便起见标题有限援助要画的每条线段都以水平依旧竖直的。水平线段用字符 - 来画,竖直线段用字符 | 来画。借使一条水平线段和一条竖直线段在有个别地方相交,则相交地点用字符 代替。
Ÿ 填充:给出填充的发端地方坐标和急需填写的字符,从初阶地点上马,用该字符填充相邻地点,直到碰到画布边缘或早已画好的线条。注意这里的邻座地点只要求思谋上下左右 4 个倾向,如下图所示,字符 @ 只和 4 个字符 * 相邻。
.*.
*@*
.*.
输入格式
第1行有四个整数m, n和q。m和n分别代表画布的肥瘦和可观,以字符为单位。q表示画图操作的个数。
第2行至第q 1行,每行是以下三种样式之后生可畏:
Ÿ 0 x1 y1 x2 y2:表示画线段的操作,和分级是线段的双方,知足要么x1 = x2 且y1 ≠ y2,要么 y1 = y2 且 x1 ≠ x2。
Ÿ 1 x y c:表示填充操作,是发轫地方,保障不会落在任何已部分线段上;c 为填充字符,是大小写字母。
画布的左下角是坐标为 的岗位,向右为x坐标增大的大势,向上为y坐标增大的来头。这q个操作根据数据提交的相继依次推行。画布最早时有所地点都以字符 .。
输出格式
出口有n行,每行m个字符,表示依次试行那q个操作后拿走的图案结果。
样例输入
4 2 3
1 0 0 B
0 1 0 2 0
1 0 0 A
样例输出
AAAA
A--A
样例输入
16 13 9
0 3 1 12 1
0 12 1 12 3
0 12 3 6 3
0 6 3 6 9
0 6 9 12 9
0 12 9 12 11
0 12 11 3 11
0 3 11 3 1
1 4 2 C
样例输出
................
... -------- ...
...|CCCCCCCC|...
...|CC ----- ...
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC|.........
...|CC ----- ...
...|CCCCCCCC|...
... -------- ...
................
评测用例规模与约定
具备的评测用例满意:2 ≤ m, n ≤ 100,0 ≤ q ≤ 100,0 ≤ x < m(x表示输入数据中全部职位的x坐标卡塔尔,0 ≤ y < n(y代表输入数据中享有职位的y坐标卡塔尔国。

AAAA
A--A

以下是我的代码

 #include<stdio.h>#include<string.h>char output[200][200];int n,m;void fill(int x,int y,char c){ output[y][x]=c; //右 if<m && output[y][x 1]!='-' && output[y][x 1]!='|' && output[y][x 1]!=c && output[y][x 1]!=' ') fill; //左 if>=0 && output[y][x-1]!='-' && output[y][x-1]!='|' && output[y][x-1]!=c && output[y][x-1]!=' ') fill; //上 if<n && output[y 1][x]!='-' && output[y 1][x]!='|' && output[y 1][x]!=c && output[y 1][x]!=' ') fill; //下 if>=0 && output[y-1][x]!='-' && output[y-1][x]!='|' && output[y-1][x]!=c && output[y-1][x]!=' ') fill;}int main(){ int q; int oper[200][5]; char temp[100]; scanf("%d %d %d",&m,&n,&q);//m 宽度 n高度 int i,j,k; int max,min; memset(output,'.',sizeof; memset(oper,0,sizeof; for(i=0;i<q;i  ) { k=0; fflush; gets; for(j=0;temp[j]!='\0' && j<20 ;j  ) { while(temp[j]!=' ' && temp[j]!='\0' && j<20) oper[i][k]=oper[i][k]*10 temp[j  ]-'0'; k  ; } } int x,y; for(i=0;i<q;i  ) { if(oper[i][0]==0) if(oper[i][1]==oper[i][3])//表示x相同 画竖线 { x=oper[i][1]; if(oper[i][2]<oper[i][4]) {max=oper[i][4];min=oper[i][2];} else {max=oper[i][2];min=oper[i][4];} for(;min<=max;min  ) if(output[min][x]=='-') output[min][x]=' '; else output[min][x]='|'; } else//表示y相同 画横线 { y=oper[i][2]; if(oper[i][1]<oper[i][3]) {max=oper[i][3];min=oper[i][1];} else {max=oper[i][1];min=oper[i][3];} for(;min<=max;min  ) if(output[y][min]=='|') output[y][min]=' '; else output[y][min]='-'; } else {//填充 x=oper[i][1]; y=oper[i][2]; fill(x,y,oper[i][3] '0'); } } for(i=n-1;i>=0;i--) { for(j=0;j<m;j  ) printf("%c",output[i][j]); printf; } return 0;}

 

16 13 9
0 3 1 12 1
0 12 1 12 3
0 12 3 6 3
0 6 3 6 9
0 6 9 12 9
0 12 9 12 11
0 12 11 3 11
0 3 11 3 1
1 4 2 C

 1 #include<iostream>
 2 using namespace std;
 3 
 4 char a[101][101];
 5 int mark[101][101];
 6 int m,n;
 7 void reMark(){
 8     for(int i=0;i<n;  i){
 9         for(int j=0;j<m;  j) mark[i][j]=0;
10     }
11 }
12 int check(int x,int y){
13     if(x<0||y<0||x>m||y>n) return 0;
14     else if(mark[y][x]==1) return 0;
15     else if(a[y][x]==' '||a[y][x]=='|'||a[y][x]=='-') return 0;
16     else return 1;
17     return 0;
18 }
19 void dfs(int x,int y,char c){
20     a[y][x]=c;
21     mark[y][x]=1;
22     if(check(x,y 1)){
23         dfs(x,y 1,c);
24     }
25     if(check(x 1,y)){
26         dfs(x 1,y,c);
27     }
28     if(check(x,y-1)){
29         dfs(x,y-1,c);
30     }
31     if(check(x-1,y)){
32         dfs(x-1,y,c);
33     }
34 }
35 void draw(int x1,int y1,int x2,int y2){
36     if(x1>x2){
37         for(int i=x1;i>=x2;--i){
38             a[y1][i]=a[y1][i]=='|'||a[y1][i]==' '?' ':'-';
39         }
40     }
41     else if(x2>x1){
42         for(int i=x2;i>=x1;--i){
43             a[y1][i]=a[y1][i]=='|'||a[y1][i]==' '?' ':'-';
44         }
45     }
46     else if(y1>y2){
47         for(int i=y1;i>=y2;--i){
48             a[i][x1]=a[i][x1]=='-'||a[i][x1]==' '?' ':'|';
49         }
50     }
51     else if(y2>y1){
52         for(int i=y2;i>=y1;--i){
53             a[i][x1]=a[i][x1]=='-'||a[i][x1]==' '?' ':'|';
54         }
55     }
56 }
57 
58 int main(){
59     for(int i=0;i<101;i  ){
60         for(int j=0;j<101;j  ){
61             a[i][j]='.';
62         }
63     } 
64     int q;
65     int x1,y1,x2,y2;
66     char c;
67     cin>>m>>n>>q;
68     for(int i=1;i<=q;i  ){
69         int operate;
70         cin>>operate;
71         if(operate==1){
72             cin>>x1>>y1>>c;
73             y1=n-1-y1;
74             reMark();
75             dfs(x1,y1,c);
76         }
77         if(operate==0){
78             cin>>x1>>y1>>x2>>y2;
79             y1=n-1-y1;
80             y2=n-1-y2;
81             draw(x1,y1,x2,y2);
82         } 
83     }
84     for(int i=0;i<n;  i){
85         for(int j=0;j<m;  j){
86             cout<<a[i][j];
87         }
88         if(i<n-1) cout<<endl;
89     }
90     return 0;
91 }

样例输入

本文由韦德国际1946英国发布于计算机网络,转载请注明出处:画图问题,计算几何

关键词: C/C++ CCF CSP试题 画图 真题 CSP

上一篇:Hadoop安全模式

下一篇:没有了