今天讲了计算几何，发几道水水的tyvj上的题解...
计算几何好难啊！@Mrs.General....怎么办....
这几道题都是在省选之前做的，所以前面的Point运算啊，dcmp啊，什么什么的，基本上没用，每次都把上次的main()函数删了接着继续写....
原谅我曾经丑出翔的代码...
虽然现在也很丑...
TYVJ 1150 绳子围点
题解：
凸包 + 凸包面积 + 皮克定理
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll; const int MAXN = + ; char cj;
int n, m; struct Point{//{{{
ll x, y; friend bool operator < (const Point& A, const Point& B){
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
} p[MAXN], ch[MAXN * ];//}}} inline ll xmult(Point a, Point b, Point c){//{{{
return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
} inline void AndrweScan(){
sort(p, p + n);
m = , ch[] = p[], ch[] = p[];
for (int i = ; i < n; i ++){
while (m >= && xmult(ch[m], ch[m - ], p[i]) > )
m --;
ch[++ m] = p[i];
} for (int i = n - ; i >= ; i --){
while (m >= && xmult(ch[m], ch[m - ], p[i]) > )
m --;
ch[++ m] = p[i];
}
}//}}} inline ll nextLL(){
bool flag = false;
do {
cj = getchar();
if (cj == '-')
flag = true;
} while (!( <= cj && cj <= )); ll ret = ;
do {
ret = ret * + cj - ;
cj = getchar();
} while ( <= cj && cj <= ); return flag ? -ret : ret;
} inline int nextInt(){
do
cj = getchar();
while (!( <= cj && cj <= )); int ret = ;
do {
ret = ret * + cj - ;
cj = getchar();
} while ( <= cj && cj <= ); return ret;
} inline ll Plot(){
ll ret = ;
for (int i = ; i < m; i ++)
ret += xmult(ch[], ch[i - ], ch[i]);
return ret;
} inline ll gcd(ll a, ll b){
return b ? gcd(b, a % b) : a;
} inline ll Cal(int i){
int j = (i == m - ) ? : i + ,
dx = ch[i].x - ch[j].x, dy = ch[i].y - ch[j].y;
return gcd(abs(dx), abs(dy));
} inline void Pick(){
ll dS = Plot(), b = , a;
for (int i = ; i < m; i++)
b += Cal(i);
a = (dS - b + ) / ;
printf("%lld\n", a + b);
} int main(){
n = nextInt();
for (int i = ; i < n; i++)
p[i].x = nextLL(), p[i].y = nextLL();
AndrweScan();
Pick();
}
TYVJ 1543 房间最短路
题解：
Floyd，dp[i][j]表示到第i面墙的第j个点的最短路，注意在更新最小值的时候判断两个点的连通
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 100000000
#define eps 1e-9 const int MAXN = ; int n;
double dp[MAXN][MAXN]; struct Point{
double x, y; friend Point operator + (const Point A, const Point B){
return (Point){A.x+B.x, A.y+B.y};
} friend Point operator - (const Point A, const Point B){
return (Point){A.x-B.x, A.y-B.y};
} friend Point operator * (const Point A, const Point B){
return (Point){A.x*B.x, A.y*B.y};
} friend Point operator / (const Point A, const Point B){
return (Point){A.x/B.x, A.y/B.y};
}
}p[MAXN][MAXN]; inline Point make_Point(double X, double Y){
return (Point){X, Y};
} inline double len(Point A){
return sqrt(A.x*A.x+A.y*A.y);
} inline bool In_region(double eg, double l, double r){
if (l>r) swap(l, r);
return (l-eps<=eg && eg<=r+eps);
} inline bool Connected(int I1, int I2, int I3, int I4){
if (I1>I3) swap(I1, I3);
if ((I1==I3 && I2==I4) || I3-I1==) return true;
double k = (p[I1][I2].y-p[I3][I4].y)/(p[I1][I2].x-p[I3][I4].x), b = p[I1][I2].y-p[I1][I2].x*k, bn;
for (int i=I1+; i<I3; i++){
bn = p[i][].x*k+b;
if (!In_region(bn, p[i][].y, p[i][].y) && !In_region(bn, p[i][].y, p[i][].y)) return false;
}
return true;
} int main(){
scanf("%d", &n); p[][] = p[][] = p[][] = p[][] = make_Point(, );
p[n+][] = p[n+][] = p[n+][] = p[n+][] = make_Point(, ); double x, in, apl;
for (int i=; i<=n; i++){
scanf("%lf", &x);
for (int j=; j<; j++)
scanf("%lf", &in), p[i][j] = make_Point(x, in);
} //init
for (int i=; i<; i++)
dp[][i] = 0.0;
for (int i=; i<=n+; i++)
for (int j=; j<; j++)
dp[i][j] = Connected(, , i, j) ? len(p[i][j]-p[][]) : INF; for (int i=; i<=n+; i++)
for (int j=; j<; j++)
for (int k=; k<i; k++)
for (int l=; l<; l++)
if (Connected(k, l, i, j)) dp[i][j] = min(dp[i][j], dp[k][l]+len(p[i][j]-p[k][l]));
apl = INF;
for (int i=; i<; i++)
apl = min(apl, dp[n+][i]);
printf("%.2lf\n",apl);
return ;
}
TYVJ 1462 凸多边形
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define eps 1e-12
using namespace std; const int MAXN = +; int n; struct Point{
long double x, y; friend Point operator - (const Point& A, const Point& B){
return (Point){A.x-B.x, A.y-B.y};
} friend long double operator * (const Point& A, const Point& B){//cross
return A.x*B.y-A.y*B.x;
} friend bool operator < (const Point& A, const Point& B){
return (A.x!=B.x) ? A.x<B.x : A.y<B.y;
} inline void print(){
cout<<setiosflags(ios::fixed)<<setprecision()<<x<<" "<<setiosflags(ios::fixed)<<setprecision()<<y<<"\n";
}
}p[MAXN], ch[MAXN]; inline int dcmp(long double eg){
if (eg>eps) return ; //>0
if (eg<-eps) return -;//<0
else return ;
} inline void GrahamScan(){
int tot, t;
sort(p, p+n); ch[] = p[], ch[] = p[], tot = ;
for (int i=; i<n; i++){
while (tot> && dcmp((ch[tot]-ch[tot-])*(p[i]-ch[tot-]))!=-) tot--;
ch[++tot] = p[i];
} t = tot, ch[++tot] = p[n-];
for (int i=n-; i>=; i--){
while (tot>t && dcmp((ch[tot]-ch[tot-])*(p[i]-ch[tot-]))!=-) tot--;
ch[++tot] = p[i];
} for (int i=; i<tot; i++)
ch[i].print();
} int main(){
scanf("%d", &n);
for (int i=; i<n; i++)
cin>>p[i].x>>p[i].y; GrahamScan();
return ;
}
TYVJ 1523 神秘大三角
题解：
这道题考的是读入...面积随便整一下就好了
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-9
using namespace std; const int MAXL = ; struct Point{
double x,y; inline void in(){
char s[MAXL];
scanf("%s",s);
int i;
x = ,y = ;
for (i=;;i++){
if (s[i]==',') break;
x *= ,x += s[i]-;
}
for (i+=;;i++){
if (s[i]==')') break;
y *= ,y += s[i]-;
} } inline void out(){
printf("%.2lf %.2lf\n",x,y);
} inline bool is_zero(){
return (y== && x==);
} inline double len(){
return sqrt(x*x-y*y);
} friend Point operator + (const Point A,const Point B){
return (Point){A.x+B.x,A.y+B.y};
} friend Point operator - (const Point A,const Point B){
return (Point){A.x-B.x,A.y-B.y};
} friend Point operator * (const Point A,const double B){
return (Point){A.x*B,A.y*B};
} friend Point operator / (const Point A,const double B){
return (Point){A.x/B,A.y/B};
} friend bool operator == (const Point A,const Point B){
return (A.x==B.x && A.y==B.y);
}
}A,B,C,D; inline double area(Point p1,Point p2,Point p3){
return abs(0.5*(p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x));
} inline bool on(Point Aa,Point Ba,Point q){
double MX = max(Aa.x,Ba.x);
double mx = min(Aa.x,Ba.x);
double MY = max(Aa.y,Ba.y);
double my = min(Aa.y,Ba.y);
return ((mx<q.x && q.x<MX) && (my<q.y && q.y<MY)) ? true : false;
} inline bool zero(double eg){
return (eg>-eps && eg<eps);
} inline int appleeeeeeee(){
A.in();B.in();C.in();D.in();
if (A==D || B==D || C==D) return ;//顶点上
double s1,s2,s3,s;
s = area(A,B,C);
s1 = area(A,B,D);
s2 = area(A,C,D);
s3 = area(B,C,D); if (zero(s1) && on(A,B,D)) return ;
if (zero(s2) && on(A,C,D)) return ;
if (zero(s3) && on(B,C,D)) return ;//边上 if ((s1+s2+s3-s)<eps && (s1+s2+s3-s)>-eps) return ;
else return ;
} int main(){
printf("%d",appleeeeeeee());
return ;
}
TYVJ 1544 角平分线
题解：
推个公式就好了
#include <cstdio>
#include <cmath> struct Point{
double x,y; inline void in(){
scanf("%lf%lf",&x,&y);
} inline void out(){
printf("%.2lf %.2lf",x,y);
} friend Point operator + (const Point A,const Point B){
return (Point){A.x+B.x,A.y+B.y};
} friend Point operator - (const Point A,const Point B){
return (Point){A.x-B.x,A.y-B.y};
} friend Point operator * (const Point A,const double B){
return (Point){A.x*B,A.y*B};
} friend Point operator / (const Point A,const double B){
return (Point){A.x/B,A.y/B};
}
}a,b,c,d; inline double len(Point eg){
return sqrt(eg.x*eg.x+eg.y*eg.y);
} int main(){
a.in();b.in();c.in();
b = b-a,c = c-a;
double AB = len(b),AC = len(c);
double cj = (AB*AC)/(AB+AC);
d = b/AB + c/AC;
d = d*cj;
d = d + a;
d.out();
return ;
}