精华内容
下载资源
问答
  • 题意:  给出平面坐标系上的n个点。  对于每个点,你可以画经过这个点的横线或竖线或什么都不画。... 将所有横坐标或纵坐标相同的两点之间连边。  对于一个连通块,设这个连通块中不...

    题目链接:http://codeforces.com/problemset/problem/870/E

    题意:

      给出平面坐标系上的n个点。

      对于每个点,你可以画一条经过这个点的横线或竖线或什么都不画。

      两条重合的直线算作一条直线。

      问你能画出多少种不同的图案。

     

    题解:

      将所有横坐标或纵坐标相同的两点之间连边。

      对于一个连通块,设这个连通块中不同的横坐标个数为sx,不同的纵坐标个数为sy。

      有可能画出的线的个数即为sx + sy。

      可以发现,如果一个联通块中有环(即siz[fa] >= sx + sy)

      那么这sx + sy条边可以同时画出。

      否则必然有一条边不能画出。

      所以当前连通块的答案:有环为2^(sx+sy),无环为2^(sx+sy) - 1。

      将所有连通块的答案乘起来即为总答案。

     

    AC Code:

      1 #include <iostream>
      2 #include <stdio.h>
      3 #include <string.h>
      4 #include <algorithm>
      5 #include <set>
      6 #define MAX_N 100005
      7 #define MAX_E 200005
      8 #define MOD 1000000007
      9 
     10 using namespace std;
     11 
     12 struct Coor
     13 {
     14     int x,y,id;
     15     Coor(int _x,int _y,int _id)
     16     {
     17         x=_x; y=_y; id=_id;
     18     }
     19     Coor(){}
     20 };
     21 
     22 int n;
     23 int par[MAX_N];
     24 int siz[MAX_N];
     25 long long ans=1;
     26 long long pw[MAX_E];
     27 Coor c[MAX_N];
     28 set<int> sx[MAX_N];
     29 set<int> sy[MAX_N];
     30 
     31 bool cmp1(const Coor &a,const Coor &b)
     32 {
     33     return a.y!=b.y ? a.y<b.y : a.x<b.x;
     34 }
     35 
     36 bool cmp2(const Coor &a,const Coor &b)
     37 {
     38     return a.x!=b.x ? a.x<b.x : a.y<b.y;
     39 }
     40 
     41 void read()
     42 {
     43     cin>>n;
     44     for(int i=1;i<=n;i++)
     45     {
     46         cin>>c[i].x>>c[i].y;
     47         c[i].id=i;
     48     }
     49 }
     50 
     51 void init_union_find()
     52 {
     53     for(int i=1;i<=n;i++)
     54     {
     55         par[i]=i;
     56         siz[i]=1;
     57     }
     58 }
     59 
     60 int find(int x)
     61 {
     62     return par[x]==x ? x : par[x]=find(par[x]);
     63 }
     64 
     65 void unite(int x,int y)
     66 {
     67     int px=find(x);
     68     int py=find(y);
     69     if(px==py) return;
     70     siz[py]+=siz[px];
     71     par[px]=py;
     72 }
     73 
     74 void build()
     75 {
     76     sort(c+1,c+1+n,cmp1);
     77     for(int i=1;i<n;i++)
     78     {
     79         if(c[i].y==c[i+1].y)
     80         {
     81             unite(c[i].id,c[i+1].id);
     82         }
     83     }
     84     sort(c+1,c+1+n,cmp2);
     85     for(int i=1;i<n;i++)
     86     {
     87         if(c[i].x==c[i+1].x)
     88         {
     89             unite(c[i].id,c[i+1].id);
     90         }
     91     }
     92 }
     93 
     94 void cal_pow()
     95 {
     96     pw[0]=1;
     97     for(int i=1;i<MAX_E;i++) pw[i]=(pw[i-1]<<1ll)%MOD;
     98 }
     99 
    100 void cal_set()
    101 {
    102     for(int i=1;i<=n;i++)
    103     {
    104         sx[find(c[i].id)].insert(c[i].x);
    105         sy[find(c[i].id)].insert(c[i].y);
    106     }
    107 }
    108 
    109 inline long long mod(long long x)
    110 {
    111     return (x%MOD+MOD)%MOD;
    112 }
    113 
    114 void cal_ans()
    115 {
    116     for(int i=1;i<=n;i++)
    117     {
    118         int fa=find(i);
    119         if(fa==i)
    120         {
    121             int edge=sx[fa].size()+sy[fa].size();
    122             if(siz[fa]>=edge) ans=mod(ans*mod(pw[edge]));
    123             else ans=mod(ans*mod(pw[edge]-1));
    124         }
    125     }
    126 }
    127 
    128 void work()
    129 {
    130     init_union_find();
    131     build();
    132     cal_pow();
    133     cal_set();
    134     cal_ans();
    135     cout<<ans<<endl;
    136 }
    137 
    138 int main()
    139 {
    140     read();
    141     work();
    142 }

     

    转载于:https://www.cnblogs.com/Leohh/p/8468731.html

    展开全文
  • 有n个点,每个点有一个$(x,y)$坐标和一个权值,任意两点之间都有连线,并且连线的权值为两个顶点的。现在直线,求穿过的直线的权值和最大为多少。 思路: 直线将这些点分成了两个部分,然后你可以发现这两...

    http://acm.hdu.edu.cn/showproblem.php?pid=6127

    题意:

    有n个点,每个点有一个$(x,y)$坐标和一个权值,任意两点之间都有连线,并且连线的权值为两个顶点的。现在画一条直线,求穿过的直线的权值和最大为多少。

     

    思路:

    直线将这些点分成了两个部分,然后你可以发现这两个部分之间所有直线的权值和为他们各部分的权值和的乘积。然后我们将所有点按极角排序,预处理一个前缀和,然后用扫描线扫描一圈即可。

    我的做法是每次扫描一下点的个数,然后利用前缀和去计算。

     1 #include<iostream>
     2 #include<algorithm>
     3 #include<cstring>
     4 #include<cstdio>
     5 #include<sstream>
     6 #include<vector>
     7 #include<stack>
     8 #include<queue>
     9 #include<cmath>
    10 #include<map>
    11 #include<set>
    12 using namespace std;
    13 
    14 #define MAXN 50005
    15 #define LL long long
    16 
    17 struct Point
    18 {
    19     LL x,y;
    20     int v;
    21     double rad;
    22     bool operator < (const Point&rhs) const
    23     {
    24         return rad < rhs.rad;
    25     }
    26 }p[MAXN];
    27 
    28 LL sum[MAXN];
    29 
    30 bool left(Point a, Point b)
    31 {
    32      return (LL)a.x*b.y - (LL)a.y*b.x >= 0;
    33 }
    34 
    35 int main()
    36 {
    37     int n,m,T;
    38     //freopen("in.txt","r",stdin);
    39     scanf("%d",&T);
    40     while(T--)
    41     {
    42         scanf("%d",&n);
    43         for(int i=0;i<n;i++)
    44         {
    45             scanf("%I64d%I64d%d",&p[i].x,&p[i].y,&p[i].v);
    46             p[i].rad = atan2(p[i].y, p[i].x);
    47         }
    48         sort(p,p+n);
    49         sum[0]=p[0].v;
    50         for(int i=1;i<n;i++)  sum[i]=sum[i-1]+p[i].v;
    51 
    52         LL ans=0;
    53         LL  L = 0, R = 0, cnt=0;
    54         while (L < n)   //每个点都尝试与原点成为分割线
    55         {
    56             if (R == L)  { R = (R + 1) % n; cnt++; }  //空区域,数量+1,后面还会减去的
    57             while (R != L && left(p[L], p[R]))   //R不等于L并且在180度之内
    58             {
    59                 R = (R + 1) % n;
    60                 cnt++;
    61             }
    62 
    63             cnt--; //分隔线旋转,原本在分隔线上的点到了右边,所以要减去
    64                    //可以理解为将该点分在分隔线的下方
    65 
    66             LL t1,t2;
    67             int num=L+cnt;
    68             if(num<n)
    69             {
    70                 t1=sum[num]-sum[L];
    71                 t2=sum[n-1]-t1;
    72                 ans=max(ans,t1*t2);
    73             }
    74             else
    75             {
    76                 t1=sum[n-1]-sum[L]+sum[num-(n-1)-1];
    77                 t2=sum[n-1]-t1;
    78                 ans=max(ans,t1*t2);
    79             }
    80             L++;   //分隔线旋转
    81         }
    82         printf("%I64d\n",ans);
    83     }
    84     return 0;
    85 }

     

    转载于:https://www.cnblogs.com/zyb993963526/p/7367728.html

    展开全文
  • ppt声音音效

    2012-10-20 08:49:08
     引导学生说出:线段有两个端点,两个端点间的线直直的,并且线段可以量出长度,还知道两点之间,线段最短,线段的长度就是两点之的距离。 多媒体课件出示:幻灯6(判断哪些是线段?) 教师:说一说我们生活中看到...
  • 可以从中选择两条线与x轴一起构成一个容器,最大的容器能装多少水? 注意:你不能倾斜容器 例如: 输入 [1,8,6,2,5,4,8,3,7] 输出: 49 解题思路: 由题述可知,两条线与x轴一起构成的容器的面积等于两条线之间的...

    题目描述:
    给定n个非负整数a1,a2,…,an,其中每个数字表示坐标(i, ai)处的一个点。以(i,ai)和(i,0)(i=1,2,3…n)为端点画出n条直线。你可以从中选择两条线与x轴一起构成一个容器,最大的容器能装多少水?
    注意:你不能倾斜容器
    在这里插入图片描述
    例如:
    输入 [1,8,6,2,5,4,8,3,7]
    输出: 49

    解题思路:
    由题述可知,两条线与x轴一起构成的容器的面积等于两条线之间的距离与两条线高度的最小值之间的乘积。
    在解答本题时并没有使用任何算法,传统的思路,一个个比较:

    class Solution {
    public:
        /**
         * 
         * @param height int整型vector 
         * @return int整型
         */
        int maxArea(vector<int>& height) {
            int output=0;
            int len=height.size();
            for(int i=0;i<len;i++){
                for(int j=i+1;j<len;j++){
                    int width=j-i;
                    int heit=min(height[i],height[j]);
                    int vol=width*heit;
                    output=max(output,vol);
                }
            }
            return output;
        }
    };
    

    note:
    其他同学的想法:从两边逼近,且每次放弃短板:

    class Solution {
    public:
        int maxArea(vector<int> &height) {
            int l,r,Max=-9999;
            for(l=0,r=height.size()-1;l<r;)
            {
                Max=max(Max,(r-l)*min(height[l],height[r]));
                height[l]<height[r]?l++:r--;
            }
            return Max;
        }
    };
    

    更简洁,在能解决问题的同时,要学会找最优解。

    展开全文
  • 然后给你,为你至少删除多少 线段们能够使这在一个矩形内。 我们知道可以确定一个矩形的,那么只需要把和这个矩形相交 的线段都删除就好了,再删除这线段是,还要删除依赖这线段的所有 ...

    题意:

    给你一个矩形,然后里面会根据规则画一些线段把这个矩形进行分割。
    但是某些线条之间会有依赖关系。然后给你两个点,为你至少删除多少
    条线段们能够使这两个点在一个矩形内。
    我们知道两个点是可以确定一个矩形的,那么只需要把和这个矩形相交
    的线段都删除就好了,再删除这条线段是,还要删除依赖这条线段的所有
    线段。所以一开始就对有依赖关系的线段用边连起来,然后删除时dfs就
    好了。

    代码:

    //
    //  Created by  CQU_CST_WuErli
    //  Copyright (c) 2015 CQU_CST_WuErli. All rights reserved.
    //
    // #include<bits/stdc++.h>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cctype>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <set>
    #include <algorithm>
    #include <sstream>
    #define CLR(x) memset(x,0,sizeof(x))
    #define OFF(x) memset(x,-1,sizeof(x))
    #define MEM(x,a) memset((x),(a),sizeof(x))
    #define For_UVa if (kase!=1) cout << endl
    #define BUG cout << "I am here" << endl
    #define lookln(x) cout << #x << "=" << x << endl
    #define SI(a) scanf("%d",&a)
    #define SII(a,b) scanf("%d%d",&a,&b)
    #define SIII(a,b,c) scanf("%d%d%d",&a,&b,&c)
    #define rep(flag,start,end) for(int flag=start;flag<=end;flag++)
    #define Rep(flag,start,end) for(int flag=start;flag>=end;flag--)
    #define Lson l,mid,rt<<1
    #define Rson mid+1,r,rt<<1|1
    #define Root 1,n,1
    #define BigInteger bign
    template <typename T> T gcd(const T& a,const T& b) {return b==0?a:gcd(b,a%b);}
    const int MAX_L=2005;// For BigInteger
    const int INF_INT=0x3f3f3f3f;
    const long long INF_LL=0x7fffffff;
    const int MOD=1e9+7;
    const double eps=1e-9;
    const double pi=acos(-1);
    typedef long long  ll;
    using namespace std;
    
    struct Line {
        int a,b,c,d;
        int flag;   // 0 vertical   1 
        void set(int _a,int _b,int _c,int _d) {
            a=_a;b=_b;c=_c;d=_d;
            if (a>c) swap(a,c);
            if (b>d) swap(b,d);
            if (a==c) flag=0;
            else flag=1;
        }
    }line[1100];
    
    int xl,yl,xr,yr;
    int n,q;
    vector<int> g[1100];
    int vis[1100];
    
    bool check(Line& x,Line& y) {
        if (x.flag==y.flag) return false;
        if ((x.b==y.b || x.b==y.d) && y.a>=x.a && y.a<=x.c) return true;
        if ((x.a==y.a || x.a==y.c) && y.b>=x.b && y.b<=x.d) return true;
        return false;
    }
    
    bool in(Line& x,int l,int r,int up,int down) {
        if (x.flag==0) {
            if (x.b<=up && x.d>=up && x.a>=l && x.a<=r) return true;
            if (x.d>=down && x.b<=down && x.a>=l && x.a<=r) return true;
        }
        if (x.flag==1) {
            if (x.a<=l && x.c>=l && x.b>=down && x.b<=up) return true;
            if (x.a<=r && x.c>=r && x.b>=down && x.b<=up) return true;
        }
        return false;
    }
    
    int dfs(int u) {
        vis[u]=1;
        int cnt=1;
        for (int i=0;i<g[u].size();++i) {
            int v=g[u][i];
            if (vis[v]) continue;
            cnt+=dfs(v);
        }
        return cnt;
    }
    
    int main(){
    #ifdef LOCAL
        freopen("C:\\Users\\john\\Desktop\\in.txt","r",stdin);
    //  freopen("C:\\Users\\john\\Desktop\\out.txt","w",stdout);
    #endif
        while (cin >> xl >> yl >> xr >> yr) {
            SII(n,q);
            rep(i,0,n) g[i].clear();
            rep(i,1,n){
                int a,b,c,d;
                SII(a,b);
                SII(c,d);
                line[i].set(a,b,c,d);
            }
            rep(i,1,n) {
                rep(j,1,n) {
                    if (check(line[i],line[j])) {
                        g[i].push_back(j);
    //                  cout << i << ' ' << j << endl;
                    }
                } 
            }
            while (q--) {
                int a,b,c,d;
                SII(a,b);SII(c,d);
                int l=min(a,c),r=max(a,c);
                int down=min(b,d),up=max(b,d);
                vector<int> v;
                rep(i,1,n) {
                    if (in(line[i],l,r,up,down)) v.push_back(i);
                }
                int ans=0;
                CLR(vis);
                for (int i=0;i<v.size();i++) if (!vis[v[i]]){
                    ans+=dfs(v[i]);
                }
                cout << n-ans+1 << endl;
            }
        }
        return 0;
    }
    展开全文
  • GSP5.exe

    2020-04-01 09:16:40
    选取圆及圆上2点作弧(从第一点逆时针方向到第二点之间的一段弧);选取圆上三点作弧(与法2相似,只是无需选中圆,作完弧后,可以隐藏原来的圆,可见新作的弧) 扇形和弓形 与三角形内部相似(先选中三个顶点),...
  • θ)所表示的直线上的,为什么说是都可以在,因为其中随便的一个可以在其他的(ρ,θ)(ρ,θ)所表示的直线上,就比如上述的(x,y)吧,它可以再很多直线上,准确的说,在经过这个的直线上,随便画两条如下: ...
  • 4、闭上一只眼睛在测试图的上方左右晃动,看到同时全黑或者全白的那条线,它前面给出的数据就是你要找的精确线数(一般精确到千分位)。如果一次没有找到,就以最接近的那个数据为基本数据输入光栅尺软件重新测试,...
  • excel的使用

    2012-11-25 17:06:01
    图8需要注意:如何确定自变量的初始值,数据点之间的步长是多少,这是要根据函数的具体特点来判断,这也是对使用者能力的检验。如果想很快查到函数的极值或看出其发展趋势,给出的数据点也不一定非得是等差的,可以...
  • 假定所有转移参数的值不变,这样一来,就可以直接用需求曲线来表达运动参数(价格P)和需求量之间的二维关系。 需求曲线具有负的斜率(反比关系),这斜线用图解方法表达了需求法则的含义:价格越高,消费者买的越...
  • 转来备用,以后慢慢学

    2010-05-21 14:14:33
    在信息面板可视的前提下,选择度量工具点击并拖出一条直线,按住Alt键从第一条线的节点上再拖出第二条直线,这样两条线间的夹角和线的长度都显示在信息面板上。用测量工具拖动可以移动测量线(也可以只单独移动测量线...
  • 天正建筑 TS4.5

    2015-10-26 17:54:24
    59.[两点尺寸]修改:回车“拾取尺寸线”,被拾取的尺寸线亮显。 60.[单词缩放]改错:“J-设基点”选项在单词非水平时出错。 61.[中心插窗][中心插门][中心高窗]改错:当插“A连续门/D等分窗”输入门窗宽带时,不再...
  • EXCEL百宝箱8.0终极版

    2011-11-05 16:48:02
    【根据工资计算钞票】:根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】:对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分工作...
  • 【根据工资计算钞票】根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分工作簿】...
  • Paint in 3D V1.9.2

    2020-08-18 18:25:49
    贯通绘制 - 使用此混合模式在个 3D 点之间绘制所有像素。这适合于非常强烈的激光光束特效,来贯穿一切。 ? 渐变绘制 - 使用此工具的任何混合模式,渐变绘制你的纹理中的所有像素。这非常适合随着时间逐渐淡化的...
  • 参数同“以单个铜公开料”一样,但在选择铜公上是一条一条地选择的,您有多少条铜公需要开料就要选择多少次,选择完后按选择的“取消”按扭或“Esc”键退出选择。 5.出放电数: ①大众化的 EDM 图纸:这是为了广大...
  • Excel百宝箱8.0

    2011-06-07 21:32:17
    【根据工资计算钞票】:根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】:对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分工作...
  • Excel百宝箱9.0无限制破解版

    热门讨论 2012-02-03 19:05:29
    【根据工资计算钞票】:根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】:对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分工作...
  • 【根据工资计算钞票】:根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】:对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分...
  • Excel百宝箱

    2012-10-27 17:09:21
    【根据工资计算钞票】:根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】:对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分工作...
  • 【根据工资计算钞票】:根据员工的工资计算需要多少张100元、50元......1元的钞票,可以批量计算。发现金工资的财务工作者必备 【隔行插入行】:对工作表隔行插入行,或者隔列插入列,其中行数可以自定义 【折分工作...

空空如也

空空如也

1 2 3
收藏数 52
精华内容 20
关键字:

两点之间可以画多少条线