首页 > 代码库 > UVALive 6263 The Dragon and the knights --统计，直线分平面

UVALive 6263 The Dragon and the knights --统计，直线分平面

2024-07-14 18:27:19   213人阅读

题意：给n条直线，将一个平面分成很多个部分，再给m个骑士的坐标，在一个部分内只要有一个骑士即可保护该部分，问给出的m个骑士是不是保护了所有部分。

解法：计算每个骑士与每条直线的位置关系（上面还是下面），用0,1表示，所以每个骑士会有一个01串，最后统计出这n条直线分成的部分数（可能有平行的），然后排序每个骑士的01串，看有多少个处在不同部分的骑士（01串不同的个数），然后比较个数关系，得出答案。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <string>#define ll long longusing namespace std;#define N 50007struct Line{    int A,B,C;}line[107];bool UPLine(Line ka,ll x,ll y){    ll res = ka.A*x + ka.B*y + ka.C;    return res > 0;}bool intersection(Line ka,Line kb){    if(ka.A*kb.B == ka.B*kb.A)        return false;    return true;}string ss[N];int main(){    int t,n,m,i,j;    int x,y;    scanf("%d",&t);    while(t--)    {        scanf("%d%d",&n,&m);        for(i=0;i<n;i++)            scanf("%d%d%d",&line[i].A,&line[i].B,&line[i].C);        string tmp = "";        for(i=0;i<n;i++)            tmp += "0";        for(i=0;i<m;i++)        {            scanf("%d%d",&x,&y);            ss[i] = tmp;            for(j=0;j<n;j++)            {                if(UPLine(line[j],x,y))                    ss[i][j] = ‘1‘;            }        }        int C = n+1;        for(i=0;i<n;i++)        {            for(j=i+1;j<n;j++)                if(intersection(line[i],line[j]))                    C++;        }        sort(ss,ss+m);        int cnt = 1;        for(i=1;i<m;i++)        {            if(ss[i] != ss[i-1])                cnt++;        }        if(cnt >= C)            puts("PROTECTED");        else            puts("VULNERABLE");    }    return 0;}
View Code

 


联系
我们