栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 1460 The Partition of a Cake

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 1460 The Partition of a Cake

#include <cstdio>#include <cstdlib>#include <cstring>#include <vector>#include <cmath>#include <algorithm>using namespace std;#define maxn 20 const double EPS=1e-5;typedef struct vect{    int x,y;    vect(int a=0, int b=0):x(a),y(b){}    vect operator-(vect a)    {        return vect(x-a.x, y-a.y);    }    int operator/(vect a)    {        return x*a.y-y*a.x;    }    bool operator==(vect a)    {        return (x==a.x && y==a.y);    }}vect;typedef struct dvect{    double x,y;    bool operator==(dvect a)    {        return (fabs(x-a.x)<EPS && fabs(y-a.y)<EPS);    }}dvect;typedef struct segment{    vect v1, v2;    bool operator==(segment a)    {        return ((v1==a.v1&&v2==a.v2)||(v1==a.v2&&v2==a.v1));    }}segment;segment seg[maxn];bool check(int i){    for (int j=0; j<i; j++)        if (seg[i]==seg[j]) return false;    if (seg[i].v1.x==seg[i].v2.x && (seg[i].v1.x==0 || seg[i].v1.x==1000)) return false;    if (seg[i].v1.y==seg[i].v2.y && (seg[i].v1.y==0 || seg[i].v1.y==1000)) return false;    return true;}int min(int x, int y){if (x>y) return y; return x;}int max(int x, int y){if (x>y) return x; return y;}int multiply(vect p1, vect p2, vect p0){    int tmp=(p1-p0)/(p2-p0);    return (tmp>0)?1:(tmp==0)?0:-1;}bool cross(segment seg1, segment seg2){    return( (max(seg1.v1.x,seg1.v2.x) >= min(seg2.v1.x,seg2.v2.x))&&     (max(seg2.v1.x,seg2.v2.x) >=min(seg1.v1.x,seg1.v2.x))&&      (max(seg1.v1.y,seg1.v2.y) >=min(seg2.v1.y,seg2.v2.y))&&      (max(seg2.v1.y,seg2.v2.y) >=min(seg1.v1.y,seg1.v2.y)) &&      (multiply(seg1.v1, seg1.v2, seg2.v1)*multiply(seg1.v1, seg1.v2, seg2.v2)<0) && (multiply(seg2.v1, seg2.v2, seg1.v1)*multiply(seg2.v1, seg2.v2, seg1.v2)<0));}dvect crossvect(segment seg1, segment seg2){    vect p1=seg1.v1, p2=seg1.v2;    vect q1=seg2.v1, q2=seg2.v2;     dvect ret;      double tmp1,tmp2;      tmp1 = (q2.x-q1.x)*(p1.y-p2.y)-(p2.x-p1.x)*(q1.y-q2.y);      tmp2 = (p1.y-q1.y)*(p2.x-p1.x)*(q2.x-q1.x) + q1.x*(q2.y-q1.y)*(p2.x-p1.x)-p1.x*(p2.y-p1.y)*(q2.x-q1.x);      ret.x = tmp2/tmp1;        tmp1 = (p1.x-p2.x)*(q2.y-q1.y)-(p2.y-p1.y)*(q1.x-q2.x);      tmp2 = p2.y*(p1.x-p2.x)*(q2.y-q1.y) + (q2.x- p2.x)*(q2.y-q1.y)*(p1.y-p2.y)-q2.y*(q1.x-q2.x)*(p2.y-p1.y);      ret.y = tmp2/tmp1;      return ret;  } int main(){    int n, ans, tmp, vnum;    dvect cp;       dvect v[maxn];    while (scanf("%d",&n)==1 && n)    {        ans=1;        for (int i=0; i<n; i++)        { scanf("%d%d%d%d", &seg[i].v1.x, &seg[i].v1.y, &seg[i].v2.x, &seg[i].v2.y); if (!check(i)) continue; tmp=0; vnum=0; for (int j=0, k; j<i; j++)     if (cross(seg[i], seg[j])){         cp=crossvect(seg[i], seg[j]);         for (k=0; k<vnum; k++)  if (cp==v[k]) break;         if (k==vnum)         {  tmp++;  v[vnum++]=cp;         }     } ans+=tmp+1;        }        printf("%dn", ans);    }    return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/375526.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号