首页 > ACM题库 > HDU-杭电 > HDU 1661 Amphiphilic Carbon Molecules -计算几何-[解题报告] C++
2013
12-21

HDU 1661 Amphiphilic Carbon Molecules -计算几何-[解题报告] C++

Amphiphilic Carbon Molecules

问题描述 :

Shanghai Hypercomputers, the world’s largest computer chip manufacturer, has invented a new class of nanoparticles called Amphiphilic Carbon Molecules (ACMs). ACMs are semiconductors. It means that they can be either conductors or insulators of electrons, and thus possess a property that is very important for the computer chip industry. They are also amphiphilic molecules, which means parts of them are hydrophilic while other parts of them are hydrophobic. Hydrophilic ACMs are soluble in polar solvents (for example, water) but are insoluble in nonpolar solvents (for example, acetone). Hydrophobic ACMs, on the contrary, are soluble in acetone but insoluble in water. Semiconductor ACMs dissolved in either water or acetone can be used in the computer chip manufacturing process.

As a materials engineer at Shanghai Hypercomputers, your job is to prepare ACM solutions from ACM particles. You go to your factory everyday at 8 am and find a batch of ACM particles on your workbench. You prepare the ACM solutions by dripping some water, as well as some acetone, into those particles and watch the ACMs dissolve in the solvents. You always want to prepare unmixed solutions, so you first separate the ACM particles by placing an Insulating Carbon Partition Card (ICPC) perpendicular to your workbench. The ICPC is long enough to completely separate the particles. You then drip water on one side of the ICPC and acetone on the other side. The ICPC helps you obtain hydrophilic ACMs dissolved in water on one side and hydrophobic ACMs dissolved in acetone on the other side. If you happen to put the ICPC on top of some ACM particles, those ACMs will be right at the border between the water solution and the acetone solution, and they will be dissolved. Fig.1 shows your working situation.

Your daily job is very easy and boring, so your supervisor makes it a little bit more challenging by asking you to dissolve as much ACMs into solution as possible. You know you have to be very careful about where to put the ICPC since hydrophilic ACMs on the acetone side, or hydrophobic ACMs on the water side, will not dissolve. As an experienced engineer, you also know that sometimes it can be very difficult to find the best position for the ICPC, so you decide to write a program to help you. You have asked your supervisor to buy a special digital camera and have it installed above your workbench, so that your program can obtain the exact positions and species (hydrophilic or hydrophobic) of each ACM particle in a 2D pictures taken by the camera. The ICPC you put on your workbench will appear as a line in the 2D pictures.

输入:

There will be no more than 10 test cases. Each case starts with a line containing an integer N, which is the number of ACM particles in the test case. N lines then follow. Each line contains three integers x, y, r, where (x, y) is the position of the ACM particle in the 2D picture and r can be 0 or 1, standing for the hydrophilic or hydrophobic type ACM respectively. The absolute value of x, y will be no larger than 10000. You may assume that N is no more than 1000. N = 0 signifies the end of the input and need not be processed. Fig.2 shows the positions of ACM particles and the best ICPC position for the last test case in the sample input.

输出:

For each test case, output a line containing a single integer, which is the maximum number of dissolved ACM particles.

样例输入:

3
0 0 0
0 1 0
2 2 1
4
0 0 0
0 4 0
4 0 0
1 2 1
7
-1 0 0
1 2 1
2 3 0
2 1 1
0 3 1
1 4 0
-1 2 0
0

样例输出:

3
3
6

从TLE的暴力枚举 到 13313MS的扫描线  再到 1297MS的简化后的扫描线,简直感觉要爽翻啦。然后满怀欣喜的去HDU交了一下,直接又回到了TLE…..泪流满面

虽说HDU的时限是2000MS 可是数据也忒强了点吧,真心给HDU跪了。

题意:给定平面上的N个点,属性分别标记为0和1,然后找一条直线,直线上的点全部溶解,一侧的1溶解,另一侧的0溶解。求出最多能溶解的点的个数。

思路:最直接的思路就是O(N^3)的暴力枚举,Discuss里面貌似有大牛过了,肯能是我太过暴力了吧,果断Tle了,然后换成了枚举单个点,然后极角排序+扫描线,

跑了13313MS。然后优化了一下跑了1297MS。下面说一下扫描线的思路。

 

首先,确定射线v1,v2与X轴正方向的角度,一个为0,一个为PI,然后同时旋转,每碰到一个点就计算一次v1,v2之间的及在两条射线上的点。

直到v1与X轴的方向 >= PI ,当前这一次计算结束,继续枚举下一个点。

这就是13313MS那份代码的思路,显然扫描线是没错的,但是有一些点被重复计算了,其实我们只需要计算α角区域内的点的个数,通过它来维

护v1,v2区域内的点的个数,优化后用时就减少到了1297MS,但是在HDU依然过不了……

POJ AC_Code 1297MS

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string>

#define LL long long
#define EPS (1e-8)

using namespace std;

const double PI = acos(-1.0);

struct P
{
    double a;
    int x,y,mark;
} pa[1010],p[1010];

double Cal_Angle(P p1,P p2)
{
    if(p1.x == p2.x && p1.y == p2.y)
        return -100.0;
    P v;
    v.x = p2.x - p1.x;
    v.y = p2.y - p1.y;
    if(p1.y <= p2.y)
        return acos(v.x/sqrt(v.x*v.x + v.y*v.y));
    return 2.0*PI - acos(v.x/sqrt(v.x*v.x + v.y*v.y));
}

void Cal_Angle(P p,P *pa,int n)
{
    for(int i = 0; i < n; ++i)
    {
        pa[i].a = Cal_Angle(p,pa[i]);
    }
}

bool cmp_angle(P p1,P p2)
{
    return p1.a < p2.a;
}

int main()
{
    int n,i,j,k,l,d;
    int Max,tl,tr,b,w,s1,s0,s2,s3;
    double xm,pil,pir;
    P vec;
    while(scanf("%d",&n) && n)
    {
        b = 0;
        w = 0;
        for(i = 0; i < n; ++i)
        {
            scanf("%d %d %d",&p[i].x,&p[i].y,&p[i].mark);
            pa[i] = p[i];
            if(pa[i].mark)
                b++;
            else
                w++;
        }

        Max = -1;

        for(i = 0; i < n; ++i)
        {
            Cal_Angle(p[i],pa,n);
            sort(pa,pa+n,cmp_angle);

            pir = pa[1].a;
            pil = pir + PI;

            s1 = s0 = s2 = s3 = 0;

            for(j = 1; j < n && pa[j].a < pil; ++j)
            {
                if(pa[j].a == pir)
                {
                    if(pa[j].mark)
                        s3++;
                    else
                        s2++;
                }
                else
                {
                    if(pa[j].mark)
                        s1++;
                    else
                        s0++;
                }
            }

            for(d = j; d < n && pa[d].a == pil; ++d)
            {
                if(pa[d].mark)
                    s3++;
                else
                    s2++;
            }

            if(pa[0].mark)
                s3++;
            else
                s2++;

            tr = s0 + (b-s1)+s2;
            tl = s1 + (w-s0)+s3;
            
            if(tr > Max || tl > Max)
            Max = tr > tl ? tr : tl;

            k = 1;

            while(pir < PI && j < n)
            {
                for(; k < n && pir == pa[k].a; ++k)
                {
                    if(pa[k].mark)
                        --s3;
                    else
                        --s2;
                }
                pir = pa[k].a;
                if(pir > PI)
                    break;
                for(l = k; l < n && pir == pa[l].a; ++l)
                {
                    if(pa[l].mark)
                    {
                        ++s3;
                        --s1;
                    }
                    else
                    {
                        ++s2;
                        --s0;
                    }
                }
                for(; j < n && pa[j].a == pil; ++j)
                {
                    if(pa[j].mark)
                    {
                        --s3;
                        ++s1;
                    }
                    else
                    {
                        --s2;
                        ++s0;
                    }
                }

                pil = pir+PI;

                for(; j < n && pa[j].a < pil; ++j)
                {
                    if(pa[j].mark)
                    {
                        ++s1;
                    }
                    else
                    {
                        ++s0;
                    }
                }

                for(d = j; d < n && pa[d].a == pil ; ++d)
                {
                    if(pa[d].mark)
                        ++s3;
                    else
                        ++s2;
                }
                tr = s0 + (b-s1)+s2;
                tl = s1 + (w-s0)+s3;
                if(tr > Max || tl > Max)
                {
                    Max = tr > tl ? tr : tl;
                }
            }
        }
        printf("%d\n",Max);
    }
    return 0 ;
}

POJ AC_Code 13313MS 

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>
#include <string>

#define LL long long
#define EPS (1e-8)

using namespace std;

const double PI = acos(-1);

struct P
{
    double x,y,a;
    int mark;
}pa[1010],p[1010];

double Cal_Angle(P p1,P p2)
{
    if(p1.x == p2.x && p1.y == p2.y)
        return -100.0;
    P v;
    v.x = p2.x - p1.x;
    v.y = p2.y - p1.y;
    if(p1.y <= p2.y)
        return acos(v.x/sqrt(v.x*v.x + v.y*v.y));
    return 2.0*PI - acos(v.x/sqrt(v.x*v.x + v.y*v.y));
}

void Cal_Angle(P p,P *pa,int n)
{
    for(int i = 0;i < n; ++i)
    {
        pa[i].a = Cal_Angle(p,pa[i]);
    }
}

bool cmp_angle(P p1,P p2)
{
    return p1.a < p2.a;
}

int main()
{
    int n,i,j,k;
    int tm1,tm0,tm2,tm3,Max,t1,t2,b,w;
    double xm,pil,pir;
    P vec;
    while(scanf("%d",&n) && n)
    {
        b = 0;
        w = 0;
        for(i = 0;i < n; ++i)
        {
            scanf("%lf %lf %d",&p[i].x,&p[i].y,&p[i].mark);
            pa[i] = p[i];
            if(pa[i].mark)
                b++;
            else
                w++;
        }

        Max = -1;

        for(i = 0;i < n; ++i)
        {
            Cal_Angle(p[i],pa,n);
            sort(pa,pa+n,cmp_angle);
            pir = pa[0].a;
            j = 1;
            while(pir <= PI && j < n)
            {
                for(;j < n && pa[j].a == pir; ++j)
                ;
                pir = pa[j].a;

                tm3 = 0;
                tm2 = 0;
                tm1 = 0;
                tm0 = 0;

                for(pil = pir+PI,k = j;pa[k].a < pil && k < n; ++k)
                {
                    if(pa[j].a == pa[k].a)
                    {
                        if(pa[k].mark == 1)
                        {
                            tm3 ++;
                        }
                        else
                        {
                            tm2 ++;
                        }
                    }
                    else if(pa[k].mark == 0)
                    {
                        tm0++;
                    }
                    else
                    {
                        tm1++;
                    }
                }
                if(pa[0].mark)
                    tm3++;
                else
                    tm2++;
                t1 = tm1+tm2+tm3 + (w-tm0-tm2);
                t2 = tm0+tm2+tm3 + (b-tm1-tm3);
                if(Max < t1 || Max < t2)
                {
                    Max = t1 > t2 ? t1 : t2;
                }
            }
        }
        printf("%d\n",Max);
    }
    return 0 ;
}

解题报告转自:http://blog.csdn.net/zmx354/article/details/15810263


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  2. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  4. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。